Linked Lists
A linked list is a set of objects where each object contains references to other objects, e.g. in the picture below the minion knows the hippo is the previous element in the list and the penguin is the next element in the list.
Similar to an array, a linked list is a linear data structure.
However, unlike arrays, the order of elements is not determined by indices. The order is determined by pointers from one object to the next.
In order to know where a list starts, we need something to point to the root of the list.
Each element, or node, in the list will store some data and store pointer information to the previous and next element in the list.
Note also, when we are searching a list, we start at the root. We will need another pointer to help us do the search. The root pointer should always tell us where the start of the list is and only be updated when necessary. Ofcourse, at the start of the search, the search pointer will be assigned the value of the root pointer..
Here is a diagram explaining the concept:
So, as you can see, we can implement a linked list as a list of Abstract Data Types (let's call them Nodes). Each node stores data and necessary pointer information.
We can implement a linked list data structure by using an ordinary array. This will allow us to use array indexing rather than messing around with memory addresses.
Because we are using the node concept, we will create an array of Node objects.
So, we should design a Node class to define Node objects. Here is some pseudocode to do this:
TYPE Node
DECLARE dataItem : INTEGER
DECLARE prevPointer : INTEGER
DECLARE nextPointer : INTEGER
END TYPE
We can now declare an array of Node objects and assign Node objects to each element in the array:
DECLARE List : Array[0:8] OF Node
List[0] ← Node(0,-1,1)
List[1] ← Node(0,0,2)
List[2] ← Node(0,1,3)
List[3] ← Node(0,2,4)
List[4] ← Node(0,3,5)
List[5] ← Node(0,4,6)
List[6] ← Node(9,5,7)
List[7] ← Node(0,6,8)
List[8] ← Node(0,7,-1)
Note that each Node stores 0. The first node's previous pointer stores -1 because there is no previous element.
Each nodes next pointer points to the next index in the array except the last one in the list.
Intro task
Design the Node class using program code. Make sure you design accessor methods for each attribute of the Node class.
Task 2 - Design Linked List class.
Design a class called LinkedList.
The class should have a constructor method that creates a 1D array of 9 nodes.
It should also have an accessor method for array of Node objects.
Task 3 - Test your design.
Write a computer program to test your design. Here is a sample program:
L = LinkedList()
nodes = L.getNodes()
for i in range(len(nodes)):
print(f"Node: {i}, DataItem: {nodes[i].getDataItem()}, Previous Pointer: {nodes[i].getPreviousPointer()}, Next Pointer: {nodes[i].getNextPointer()}")
Task 4 - Search the Linked List for an item of data
Now let's search the list for an item.
The logic is:
- Create a new pointer to do the search and assign it a value of rootPointer (0)
- While the current Node data item at the index of the search pointer doesn't equal the item being searched for and the search pointer isn't null, update the search pointer to store the value of the current node's next pointer!
Create a procedure in the LinkedList class that will search for an item. If it finds the item, a message Item found! is displayed, else Item not in list :( is displayed.