---
slideOptions:
theme: white
---
# Chapter 12 - Linked List
###### tags: `Data Structure and Algorithms`
---
## Learning objectives
By the end of this chapter, you should able to:
1. Construct a linked list with appropriate arrays and nodes
2. Explain the linked list operation, i.e. Insertion and deletion
3. Describe different types of linked list, i.e. circularly-linked list and doubly-linked list
4. List out the daily application of linked lists
## Introduction
We can construct an array for storing more than one value. However, it is difficult to add and delete values in an array because _shifting_ is a time-consuming action in an array. We can use linked lists to solve this problem, but the level of implementation is higher.
Compared with arrays, linked lists have the following advantages.
1. **Flexibility** : when declaring an array list, some memory space is pre-allocated to hold the largest list possibly needed in a particular application. The dynamic storage for linked lists eliminates the overflow problem until it is actually exhausted.
2. **Time** : insertions and deletions can be made more easily. When a new element is inserted, some other elements might have to be shifted in order to have space for a new element in a specific list position. In the linked list, no element shifting is necessary; instead, a pointer redirection is used.
A linked list is constructed with the objects, which will be covered in the later section.
## Basic concept
### Nodes and linked list
A _node_ is a basic element in a linked list, which is a _structure_ with a pointer and the same data type as the node. The following shows a diagrammatic example.
The nodes can be linked together with the pointers. The first node is usually a pointer to the node type.
The _pointer_ is implemented by the array indices in the array implementation, while that is an object reference in dynamic memory implementation.
### Basic Operation
There are _three_ operations in a linked list, namely _insertion_, _deletion_ and _swap_.
Assuming that there is a linked list as shown below.
#### Insertion
Assume we need to add "Data 4" in between "Data 2" (previous node) and "Data 3" (next node). There are several steps to finish it.
1. Prepare a new node with data.
2. Set the pointer to the previous node (i.e. Data 2).
3. Set the link of the new node to the next node (i.e. Data 3).
4. Set the link of the previous node (i.e. Data 2) to the new node.
Notice that when memory is exhausted, the insertion is in an _overflow_ state.
#### Deletion
Assume that we need to delete "Data 2", which is in between "Data 1" (previous node) and "Data 3" (next node).
1. Point at the previous node.
2. Set the link of the previous node to the next node.
Notice that if there is no node inside the linked list, the deletion is in an _underflow_ state.
#### Swap
Assume that we need to swap "Data 1" (previous node) and "Data 2" (next node).
1. Create a new node
2. Set the pointer to the previous node (i.e. Data 1)
3. Copy the content of the previous node (Data 1) to the new node
4. Copy the content of the next node (Data 2) to the previous node
5. Copy the content of the new node to the next node
## Array Implementation
We first look at the implementation of a linked list with an array for an easier understanding of linked lists.
### Node and linked list
In array implementation, the nodes are created with a nested list in Python. Below shows an example of the code of a node with two values, i.e. id and name.
The array structure has two basic fields: the data and the next index location. The next index field allows the array structure to take on the attributes of a list. A list array is shown below.
Notice that the array index -1 refers to the end of the linked list.
We can use the following Python code to create the above linked list.
```python=
LinkedList = [
["Data 3", 9], # [0]
[None, 3], # [1]
["Data 1", 6], # [2]
[None, 7], # [3]
[None, 1], # [4]
[None, -1], # [5]
["Data 2", 0], # [6]
[None, 8], # [7]
[None, 5], # [8]
["Data 4", -1] # [9]
]
head = 2
```
Note that there are actually two lists in the array. The data list starts as element 2 and progresses through 6 and 0 and to the end of the data at element 9. The second list links all of the empty or available elements together. It starts at element 4, progresses through 1, 3, 5, and 8, and ends at 5. The link list is ended with index -1, or any other values that are not within the array index.
Of course, we can use dictionaries instead of lists. The implementation is almost the same, and leave it as your exercise.
#### Display the linked list
If we use a diagram to show the list in the above diagram, it should look like as shown below.
Before implementing an algorithm, we usually write down the pseudocode first. We can display the list by the following algorithm.
```
Algorithm display (list, start)
Display the linked list on the screen.
list list is metadata structure to a valid list
start start is pointer to the head of list
1 set next to start
2 while the index of the node > -1
display the node data
set next to the next index of the node
# At this point, the pointer is pointing to the last
node. However, the last node is not displayed.
3 print out the last node data
```
The above algorithm is implemented in Python as shown below.
```python!
def display(list, start):
"""
The function is used to display the list,
concatenate with " -> "
Args:
list: The list being displayed
start (int): The head of the list
"""
next = start
while LinkedList[next][1] > -1:
print(LinkedList[next][0], end=" -> ")
next = LinkedList[next][1]
print(LinkedList[next][0])
```
To insert new data from the linked list, just simply change the link index. The operation is similar to that of using dynamic memory implementation.
We can print out the list by calling the display method.
```python!
display(LinkedList, head)
```
Output:
```
Data 1 -> Data 2 -> Data 3 -> Data 4
```
In the above code, _docstring_ is used in [_Google Style_](https://google.github.io/styleguide/pyguide.html#Comments). They are bounded by the triple single quotes (''') or triple double quotes (""") symbols. We can print out the documentation by using _FunctionName_.\_\_doc\_\_.
```python!
print(display.__doc__)
```
Output:
```
The function is used to display the list,
concatenate with " -> "
Args:
list: The list being displayed
start (int): The head of the list
```
Documentation files can be generated automatically by writing the docstring.
### Basic operation
#### Insertion
To insert a new node, it is required to do the following actions.
1. Find the insertion point with the index
2. Point the new node to its successor by changing the index
3. Point the predecessor to the new node by changing the index
The pseudocode of the _insertion_ algorithm is as shown below.
```
Algorithm insert (list, new, pre, dataIn)
Insert data into a new node in the list
Pre list is metadata structure to a valid list
new is the index to data in the list
pre is index to data's logical predecessor
dataIn contains data to be inserted
Post data have been inserted in sequence
Return True if successful, (False if memory overflow)*
1 create a new node
2 set the link of the new node to the next node
3 set the link of the previous node to the new node
4 return True
* Need to use another method to check the availability,
that is not being implemented in this algorithm
```
For example, we need to insert "Data 5" in between "Data 2" and "Data 3". We know that the index of "Data 2" is [6].
Below shows the diagrams of insertion with the algorithm.
With the above pseudocode and diagram, we can try to implement the algorithm in Python as follows.
```python!
def insert(list, new, pre, dataIn):
"""
The function is used to insert a new value
into the list
Args:
list: A valid list
New (int): The index of new node
pre (int): The index to predecessor
dataIn: Data to be inserted
"""
node = [dataIn, None]
list[new] = node
node[1] = list[pre][1]
list[pre][1] = new
return True
```
We can try the algorithm by displaying the list again.
```python!
display(LinkedList, head)
insert(LinkedList, 1, 6, "Data 5")
display(LinkedList, head)
```
Output:
```
Data 1 -> Data 2 -> Data 3 -> Data 4
Data 1 -> Data 2 -> Data 5 -> Data 3 -> Data 4
```
Unfortunately, we may get something wrong if we try to add it as the beginning of the list.
```python!
display(LinkedList, head)
insert(LinkedList, 1, head, "Data 5")
display(LinkedList, head)
```
Output:
```
Data 1 -> Data 2 -> Data 3 -> Data 4
Data 1 -> Data 5 -> Data 2 -> Data 3 -> Data 4
```
Notice that the head is pointing to the first node. The meaning of the above program fragment is actually adding a new node _after_ the head.
To solve this problem, we need to create one more function insertBegin, as shown below.
```python!
def insertBegin (list, start, new, dataIn):
"""
The function is used to insert a new value
into the beginning of the list
Args:
list: A valid list
start (int): The index of the starting node
New (int): The index of new node
dataIn: Data to be inserted
"""
node = [dataIn, None]
list[new] = node
node[1] = start
return new
```
We can try the algorithm again.
```python!
display(LinkedList, head)
head = insertBegin(LinkedList, head, 1, "Data 6")
display(LinkedList, 1)
```
Output:
```
Data 1 -> Data 2 -> Data 3 -> Data 4
Data 6 -> Data 1 -> Data 2 -> Data 3 -> Data 4
```
#### Deletion
Similar to insertion, we just need to update the index for deletion, instead of really removing the value. Below algorithm in pseudocode shows the deletion of "Data 5" in the above linked list.
```
Algorithm delete (list, start, dataOut)
Insert data into a new node in the list
Pre list is metadata structure to a valid list
dataOut contains data to be deleted
Post data have been deleted in sequence
Return True if successful, (False if underflow)*
1 Find out the node
2 set the link of the previous node to the next node
3 return True
* Need to use another method to check the availability,
that is not being implemented in this algorithm
```
For the first line "Find out the node", we need to use a searching method. In this chapter, we assume that the value of dataOut must exist in LinkedList, and we use a while loop to search the record. The algorithm will not be explained in this chapter.
Below shows the diagrams of deletion with the algorithm.
With the above pseudocode and diagram, we can try to implement the algorithm in Python as follows.
```python!
def delete(list, start, dataOut):
"""
The function is used to delete a specific
value from the list
Args:
list: A valid list
start (int): The head of the list
dataOut: Data to be deleted
"""
pre = 0
loc = start
while list[loc][0] != dataOut:
pre = list[start][1]
loc = list[loc][1]
list[pre][1] = list[loc][1]
return True
```
We can try the algorithm by displaying the list again.
```python!
display(LinkedList, head)
delete(LinkedList, head, "Data 5")
display(LinkedList, head)
```
Output:
```
Data 1 -> Data 2 -> Data 5 -> Data 3 -> Data 4
Data 1 -> Data 2 -> Data 3 -> Data 4
```
#### Swap
It is relatively easy to swap data in array implementation in Python. What we need to do is to swap the data inside the nodes.
For example, if we need to swap "Data 2" (`[6]`) and "Data 3" (`[0]`), we can use the following statement.
```python!
LinkedList[6][0], LinkedList[0][0] = LinkedList[0][0], LinkedList[6][0]
```
The output should look like this.
Of course, we can write an independent function to swap the node. It would be your exercise.
```python!
display(LinkedList, head)
LinkedList[6][0], LinkedList[0][0] = LinkedList[0][0], LinkedList[6][0]
display(LinkedList, head)
```
Output:
```
Data 1 -> Data 2 -> Data 3 -> Data 4
Data 1 -> Data 3 -> Data 2 -> Data 4
```
## Dynamic memory implementation(\*)
### Node and linked list
In dynamic memory implementation, a node is created by an object. Below shows an example of the code for a node.
We will create one more class for the linked list.
The nodes can be linked together with the pointers. The first node is usually a pointer with the node type.
For example, we need to initialise a linked list as shown below.
For easier understanding, we use the following Python code to initialise a linked list fist.
```python!
node1 = Node("Data 1")
node2 = Node("Data 2")
node3 = Node("Data 3")
node4 = Node("Data 4")
list = LinkedList()
list.head = node1
node1.next = node2
node2.next = node3
node3.next = node4
```
#### Display linked list
We can display the linked list by the following algorithm.
```python!
Algorithm display ()
Display the linked list on the screen.
1 set node to start
2 while the next node is not None
display the node data
set node to the next node
3 print out the last node data
```
The above algorithm is implemented in Python as shown below.
```python!
def display(self):
"""
The function is used to display the list,
concatenate with " -> "
"""
node = self.head
while node != None:
print(node.value, end=" -> ")
node = node.next
print(node.value)
```
Note that the method is put inside the LinkedList class.
We can print out the linked list by calling the display method.
```python!
list.display()
```
Output:
```
Data 1 -> Data 2 -> Data 3 -> Data 4
```
### Basic Operations
There are three basic operations for a linked list, namely _insertion_, _deletion_ and _swap_. We will only focus on the first two in this section. The implementation of _swap_ will be reserved for your exercise.
#### Insertion
To insert a new node, it is required to do the following actions.
1. Find the insertion point with the object reference(s)
2. Point the new node to its successor
3. Point the predecessor to the new node
The pseudocode for the _insertion_ algorithm is as shown below. Unlike the array implementation, we can find insert as the first node in the same method.
```
Algorithm insert (pre, dataIn)
Inserts data into a new node in the list.
Pre pre is pointer to data’s logical predecessor
dataIn contains data to be inserted
Post data have been inserted in sequence
Return true if successful, false if memory overflow
1 create a new node
2 set new node data to dataIn
3 if pre is the head nodde
Adding before first node or to empty list.
1 set new node link to list head
2 set list head to the new node
4 else
Adding in middle or at end.
1 set new node link to previous node link
2 set previous node link to the new node
5 end if
6 return true
end insert
```
Be noticed that when memory is exhausted, the insert is in an _overflow_ state.
Below shows the diagram of insertion with the algorithm, assuming there are two cases,
1. "Data 5" is inserted as the beginning of the list
2. "Data 5" is inserted between "Data 2" and "Data 3".
With the above pseudocode and diagram, we can try to implement the algorithm in Python.
```python!
def insert(self, pre, dataIn:
"""
The function is used to delete a specific
value from the list
Args:
pre: The pointer to the previous
dataOut: Data to be deleted
"""
newNode = Node(dataIn)
if pre == self.head:
newNode.next = pre
self.head = newNode
else:
newNode.next = pre.next
pre.next = newNode
return True
```
We can try the algorithm by displaying the list again.
```python!
list.display()
list.insert(node2, "Data 5")
list.display()
list.insert(list.head, "Data 6")
list.display()
```
Output:
```
Data 1 -> Data 2 -> Data 3 -> Data 4
Data 1 -> Data 2 -> Data 5 -> Data 3 -> Data 4
Data 6 -> Data 1 -> Data 2 -> Data 5 -> Data 3 -> Data 4
```
#### Deletion
Similar to insertion, we just need to update the object reference for deletion. We do not need to remove the value. Below shows the algorithm in pseudocode.
```
Algorithm delete (dataOut)
Deletes data from list & returns it to calling module
Pre dataOut is variable to receive deleted data
Post return True if data have been deleted
1 if head node value is dataOut
2 set head node pointing to next node
2 else
1 search the previous node
2 set previous node pointing to next node
3 end if
4 return True
end delete
```
The following shows the diagrammatic presentation of the _deletion_ algorithm.
Similarly, we can implement the algorithm in Python with the above pseudocode.
```python!
def delete(self, dataOut):
"""
The function is used to delete a specific
value from the list
Args:
pre: The pointer to the previous
dataOut: Data to be deleted
"""
node = self.head
if node.value == dataOut:
self.head = node.next
else:
while node.next.value != dataOut:
node = node.next
node.next = node.next.next
return True
```
We can try the algorithm as shown below.
```python!
list.display()
list.insert(node2, "Data 5")
list.display()
list.insert(list.head, "Data 6")
list.display()
list.delete("Data 5")
list.display()
```
Output:
```
Data 1 -> Data 2 -> Data 3 -> Data 4
Data 1 -> Data 2 -> Data 5 -> Data 3 -> Data 4
Data 6 -> Data 1 -> Data 2 -> Data 5 -> Data 3 -> Data 4
Data 6 -> Data 1 -> Data 2 -> Data 3 -> Data 4
Data 1 -> Data 2 -> Data 3 -> Data 4
```
## Application
In the hard disk, the data of a file is stored in different tracks and sectors, instead of consecutive tracks and sectors. However, they are required to be put into memory in order.
The sectors are linked up as a linked list, and the head is pointed by a pointer in the disk directory (i.e. the file names and pointers). Hence, all files cannot be read successfully after the disk directory is deleted.
## Variant of linked list
Besides the basic linear linked list, there are several kinds of linked list. In this chapter, the _circularly-linked list_ and _doubly-linked list_ are going to be discussed.
### Circularly-linked list
Circularly-linked list is a linked list that the last node's link points to the first node of the list. It is able to traverse the list starting at any point, and allows quick access to the first and last records through a single pointer.
### Doubly-linked list
Each node in doubly-linked list has a pointer to both its successor and its predecessor. This structure will allow searching in both directions. It is easier to manipulate insertion or deletion of a node given only that node's address.
Sign in with Wallet
Connect another wallet