The list ADT represents a countable number of values that can occur more than once. Lists are a finite sequence and are supported by a great many programming languages, and items in the list are separated by comma’s, semicolons etc.
With linked lists, the size of the list can change. In a linked list, values are stored in nodes. Each node is comprised of the data, and a reference to where in the memory the next node is. This means that items within the lists don’t have to be next to each other in memory, because each node has a pointer that will point to the address where the next value is stored, unlike arrays which require all values to exist consecutively in a list.
Below is a visual example of two types on linked lists: a singly-linked list, which only has a pointer to the next value, and a doubly-linked list, which has a pointer for the previous value as well.
Figure One: https://webcms3.cse.unsw.edu.au/COMP1927/16s1/resources/2468
In a linked list, the following can be done:
- Check to see if it is empty
- Access a node within the list
- Traverse the list
- Check the size of the list
- Insert and Remove from the list
Below, I will talk about how values are added and removed from a linked list.
Adding to a Linked List
To add a value to the start of the list, you would begin by using the push function to add the node. After that you would allocate the node and the data for the new node, and then make the next for the new node head, before finally moving the head to the point of the new node. This would insert a new node to the start of the linked list.
def push(self, new_data):def push(self, new_data):
new_node = Node(new_data)
new_node.next = self.head
self.head = new_node
Figure Two: https://www.geeksforgeeks.org/linked-list-set-2-inserting-a-node/
In order to add a new node at a later point within the list, you would specify where the new node goes by first specifying what the soon to be previous node is called. If that node exists, you would go on to create the new node and the data for the new node. Finally, you would set the next of the new node to the next of the previous node, before changing the next of the previous node to be the new one. By doing it this way, it will ensure the list remains in the correct order. The code for this is as follows:
def insertAfter(self, prev_node, new_data):
if prev_node is None:
print "The given previous node must inLinkedList."
return
new_node = Node(new_data)
new_node.next = prev_node.next
prev_node.next = new_node
Figure Three: https://www.geeksforgeeks.org/linked-list-set-2-inserting-a-node/
Adding to the beginning of a linked list is significantly easier than adding at any other point, as adding a value to the start requires creating the new value, and then having a pointer that points to what was originally the first value. Adding anywhere else requires changing multiple pointers.
Removing From a Linked List
In a linked list, a value can be removed from the start of the list by having the head of the list point to node where you wish to start. For example, if you had a linked list and wanted to remove the first thing in the list, you would have the list point to the second value first. If you wish to remove the second value, you would link the first values next node to the third value. This will work when deleting any node anywhere within the list.
Difference to Arrays
A linked list is different to an array, because an array will take up a continuous set of locations in memory, whereas a linked list does not require the values to be next to each other in memory. Furthermore, you can add as much to a linked list as you need to, as you can change the length after creation. Arrays only have a finite length but will reserve some memory locations for any additions to the list, but once you have filled all locations in memory that are being used for that array, you must copy the array to continue adding to it.
Also, in terms of accessing a value in an array versus accessing a value in a list, it is cheaper to access one in an array. If you wanted to access the 5th value in an array, you would simply start from the first address of the array and add 4. This would access the fifth value straight away. In a linked list, you would need to work through the list to get to the fifth value; so value one has a point that goes to value two, go to where value two is and find the pointer for value three, so on and so forth.
Recursion in Linked Lists
In a linked list, recursion can be used to both find the length of the list, as well as the sum of the values within the list.
To understand recursion in this sense, we must first understand what recursion is.
Recursion can be seen as an if statement. It is a function that will call itself continually until it reaches a point where it has been programmed to no longer do so. Recursion usually works by making the problem that you are trying to solve, such as finding out the sum of all the values in the linked list, smaller and smaller until it can easily be solved, then working its way back up.
If you wanted to see the sum of the values in the linked list, you could do this by writing recursive function that will return the value of the current node and add it to the sum of the previous nodes, then move on to the next node until the value of a node reads none. In that event, the function will return 0 and stop carrying out the function.
To find the length of a linked list through recursion, you would have a recursive function that would add one to the count of how many nodes there have been each time there is a new node, and stop if the head of the next node is NULL – that is, that there isn’t another node after the previous one that the function added.
Data Structures and Algorithms - Amy Senior 