Searching Linked Lists
So, we can implement a Linked List by using a 1D array.
Click the button to view some sample code. Paste it in your IDE to see it in action. Edit the code if you have any ideas to help you understand it more.
There is a Node class, LinkedList class and some test code creating an instance of a LinkedList object.
Note: this can be mind-bending. Take some time to think about it and talk about it with your group. Use a whiteboard or pencil/paper if it will help you visualize the concept.
The above sample is very convenient. Node 0 points to Node 1. Node 1 points to Node 2. Node 2 points to Node 3 etc.
Let's mess around with the order by changing the previousPointer and nextPointer values in each node. This has been prearranged so it should work.
Replace the code in the ###---------### section with this:
self.__nodes.append(Node(-1,2,23))
self.__nodes.append(Node(2,3,44))
self.__nodes.append(Node(0,1,66))
self.__nodes.append(Node(1,5,92))
self.__nodes.append(Node(7,6,71))
self.__nodes.append(Node(3,7,32))
self.__nodes.append(Node(4,-1,1))
self.__nodes.append(Node(5,4,17))
Run the code again.
What do you notice?
Now, We will search the list for a specific value.
Becuase we are searching from the start of the list, we don't need to pay attention to the previous pointer stored in each Node.
Let's look a structured English algorithm:
- SET a root pointer to the start of the list eg index 0.
- SET a search pointer to the root pointer.
- REPEAT the following step UNTIL the data item is found or search pointer has reached the end of the list.
- IF the data item at the current Node pointed to by the search pointer is not the same as the search item, update the search pointer to be the next pointer of the current node!
- OUTPUT the data item if it was in the list or a message "Not in List" if the data item was not found.
Here is a suggested solution in PSEUDOCODE. Try to implement the design yourself first.
Code this in Python, adapting from the code above. ie keep the 2 class definitions and rewrite the test program.
Can you understand the logic behind this algorithm?
If you can, you are on your way!
If you can't, don't panic. It may take a little time to become understandable.
See if you can rebuild the whole prgram from scratch.