8 Pages921 Words228 Views
|
|
|
Algorithms for Linked ListsAlgorithms shown below use two data structures: DATA and LINK. Both datastructures are single dimensional arrays. DATA holds actual items and LINKcontains "pointers" to DATA items.Furthermore, two abstractions are utilised to create and remove items in a linked list.They are GETNODE and RET respectively (refer to the handout for their details).They are essentially storage pool operations.Algorithm 1: Create a linked list with two items- In this algorithm we create alinked list with two items.procedure create2(INOUT start)declare pointercall GETNODE(pointer) // get an available nodestart pointer; DATA(pointer) "FIRST";call GETNODE(pointer) // get a second available nodeLINK(start) pointerLINK(pointer) 0; DATA(pointer) "SECOND"end // end of procedure Start Data Link Data Link0SECONDFIRST
Algorithm 2: Calculate the number of items in a linked listfunction howMany(IN Start)declare count, pointerif Start = 0 then return 0else [pointer start; count 0 while pointer 0 do count count + 1 pointer LINK(pointer) end return count ]end // end of procedureA recursive version of the above algorithm can be written as below:function howMany(IN Start)if Start = 0 then return 0else return 1 + howMany(LINK(pointer))end // end of procedure
Algorithm 3: Display the data items in a linked listprocedure display(IN start)declare pointerpointer startwhile (pointer 0) do print(DATA(pointer)) pointer LINK(pointer)endend // end of procedureAlgorithm 4: Merge two linked listsprocedure concatenate(IN list1, IN list2, OUT newList) declare pointercase : list1 = 0: newList list2 : list2 = 0: newList list1; : else: [pointer list1; newList list1; while LINK(pointer ) 0 do pointer LINK(pointer) end LINK(pointer) list2 ]endend // end of procedure

## End of preview

Want to access all the pages? Upload your documents or become a member.

Related Documents

### Support

#### +1 306 205-2269

Chat with our experts. we are online and ready to help.