logo

Algorithms - Data Structures | DATA & LINK

   

Added on  2019-09-30

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
CSCI 103 Algorithms and Problem Solving
|4
|395
|426

Iterative Version for Reversing a Singly Linked List
|5
|504
|399

Data Structure - Assignment
|9
|1398
|163

Programming, Algorithms and Data Structure: Weekly Tasks and Exercises
|2
|501
|348