Algorithms for Linked Lists: Creation, Traversal, and Item Management

This assignment presents a comprehensive exploration of linked list algorithms, encompassing ten distinct procedures designed to manipulate and manage linked list data structures. The algorithms cover fundamental operations such as creating a linked list with two items, calculating the number of items, displaying data items, merging two linked lists, inserting items at the beginning, searching for specific items, deleting items, deleting an item at a specific position, deleting all instances of a given item, and inverting the linked list. The solutions, including those provided by Samuel Wiser and Patrick McGill, demonstrate diverse approaches to achieve the desired functionalities. These algorithms utilize data structures like DATA and LINK arrays, along with GETNODE and RET abstractions for node management. The assignment provides valuable insights into linked list implementations and their practical applications in data management and algorithm design.

Algorithms for Linked Lists
Algorithms shown below use two data structures: DATA and LINK. Both data
structures are single dimensional arrays. DATA holds actual items and LINK
contains "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 a
linked list with two items.
procedure create2(INOUT start)
declare pointer
call GETNODE(pointer) // get an available node
start  pointer; DATA(pointer)  "FIRST";
call GETNODE(pointer) // get a second available node
LINK(start)  pointer
LINK(pointer)  0; DATA(pointer)  "SECOND"
end // end of procedure
Start
Data Link Data Link
FIRST SECOND 0

Algorithm 2: Calculate the number of items in a linked list
function howMany(IN Start)
declare count, pointer
if Start = 0 then
return 0
else
[pointer  start; count  0
while pointer  0 do
count  count + 1
pointer  LINK(pointer)
end
return count
]
end // end of procedure
A recursive version of the above algorithm can be written as below:
function howMany(IN Start)
if Start = 0 then return 0
else
return 1 + howMany(LINK(pointer))
end // end of procedure

Algorithm 3: Display the data items in a linked list
procedure display(IN start)
declare pointer
pointer  start
while (pointer  0) do
print(DATA(pointer))
pointer  LINK(pointer)
end
end // end of procedure
Algorithm 4: Merge two linked lists
procedure concatenate(IN list1, IN list2, OUT newList)
declare pointer
case
: 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
]
end
end // end of procedure

Algorithm 5: Inserting an item to the beginning of a linked list
procedure insertBeginning(INOUT start, IN item)
declare pointer
call GETNODE(pointer)
DATA(pointer)  item
LINK(pointer)  start
start  pointer
end // end of procedure
Algorithm 6: Search an Item in a linked list
function isItemIn(IN start, IN item)
declare pointer, found
pointer  start
found  false
while pointer  0 do
if DATA(pointer) = item then
found  true
else
pointer  LINK(pointer)
end
return found
end // end of procedure

Algorithm 7: Delete an item from a linked list
procedure deleteItem(INOUT start, IN item)
declare pointer, previous, found
if start  0 then
[pointer  start; previous  start
found  false
while pointer  0 and NOT found do
if item = DATA(pointer) then
[found  true
if start = pointer then
start  LINK(pointer)
else
[LINK(previous)  LINK(pointer)
] // end if
RET(pointer) // garbage collection
]
else
[previous  pointer
pointer  LINK(pointer)
] // end if
end // end of while
] //end if
end // end of procedure

Algorithm 8: Delete an item and its specific position in a linked list, remove
that item from the link list
Solution 1 (Samuel Wiser)
procedure delete (IN OUT start, IN position)
count  1
if (position = 1) then
start  LINK(start)
else
next  start
while (count < (position – 1)) do
next  LINK(next)
count  count + 1
endwhile
LINK(next)  LINK(LINK(next))
endif
end
Solution 2 (Patrick McGill)
Procedure Delete At(IN/OUT start, IN position)
Counter  1
pointer start
if (position =1) then start  link (start)
else
while(counter ≠ position)
lastposition  pointer
pointer link (pointer)
counter =counter +1
endwhile
if( pointer =0) then
link (lastposition) = 0
else
link (lastposition ) link (pointer)
endif
endif
endproc

Algorithm 9: Delete all instances of a given item from a linked list
Procedure deleteAll(INOUT start, IN item)
declare pointer, last
pointer ← start
last ← start
while (pointer ≠ 0)
if DATA(pointer) = item
if pointer = start then
[start ← LINK(pointer)
last ← pointer
pointer ← LINK(pointer)
]
else
[
LINK(last) ← LINK(pointer)
pointer ← LINK (pointer)
]
else
[
last ← pointer
pointer ← LINK(pointer)
]
end
end

Algorithm 10: Invert
procedure invert(INOUT start)
declare p, q, r
p  start; q  0
while p  0 do
r  q; q  p //r follows q; q follows p //
p  LINK(p)
LINK(q)  r
end
start  q
end //end of procedure