A linked list is composed of nodes, where each node contains an element, and each node is connected to its next neighbor.
The figure above shows that there are three nodes in the linked list.
And a node can be defined as below:
|
class Node: def __init__(self, element): self.elmenet = element self.next = None |
The variable head denotes the first node in the list, while the variable tail denotes the last node in the list. If the list is empty, both head and tail are set to None.
1. How it works?
When a list is empty, both the head and tail variables point to None.
In order to add nodes into a list, first of all create the first node:
The head variable points to Node 1, and similarly, the tail variable also points to Node 1.
|
head = Node("Atlanta") tail = head |
Next, create the second node and add it to the list.
Node 2 is succeeded by Node 1, updating the next pointer of Node 1 and the tail as follows: The next pointer of Node 1 now directs to Node 2, and likewise, the tail variable also points to Node 2.
|
tail.next = Node("Macon") tail = tail.next |
Next, create the third node and add it to the list.
Node 3 is followed by Node 2, updating the next pointer of Node 2 and the tail as follows: The next pointer of Node 2 now points to Node 3, and similarly, the tail variable also points to Node 3.
|
tail.next = Node("Dallas") tail = tail.next |
To traverse elements in the list, you can follow these steps:
- Start from the head of the list.
- Access the element of the current node.
- Move to the next node using the next
- Repeat steps 2 and 3 until you reach a node where the next pointer is None, indicating the end of the list.
|
current = head while current != None: print(current.elmenet) current = current.next |
2. Basic operations of a linked List:
- addFirst: Add a node to the head of the list
- addLast: Add a node to the tail of the list
- insert: Add a node at the specified index
- removeFirst: Remove the first node in the list
- removeLast: Remove the last node in the list
- removeAt: Remove the node at the specified index
3. Method Implementation
a. addFirst
When adding a node to the current list at the first position, please follow this procedure:
Initially, generate a new node, for instance, the "Chicago" node.
| newNode = Node(e) |
Insert the new node, "Chicago", at the beginning of the list before the first node, "Atlanta".
| newNode.next = self.__head |
The head variable is updated to point from the "Atlanta" node to the "Chicago" node.
| self.__head = newNode |
If the new node is added to an empty list, then it becomes the only node in the list.
| if self.__tail == None: self.__tail = self.__head |
b. addLast
When adding a node to the current list at the last position, please follow this procedure:
Initially, generate a new node, for instance, the "Chicago" node.
| newNode = Node(e) |
If the new node is added to an empty list, then it becomes the only node in the list.
| if self.__tail == None: self.__head = self.__tail = newNode |
Otherwise, insert the new node, "Chicago", after the last node, "Dallas".
| self.__tail.next = newNode |
And then, update the tail variable to point from the node "Dallas" to the new node "Chicago".
| self.__tail = self.__tail.next |
c. insert(index, e)
When inserting a node to the current list at the specified index, please follow this procedure:
An index of 0 indicates that the new node is added to the first position in the list.
| if index == 0: self.addFirst(e) # Insert first |
If the index is greater than or equal to the number of nodes in the list, it indicates that the new node is added to the last position in the list.
|
elif index >= self.__size: self.addLast(e) # Insert last |
When inserting a new node in the middle of the list, declare a variable, current, and point it to the head node.
| current = self.__head |
Iterate through the nodes using a loop while moving to the previous node until the desired index is reached.
|
for i in range(1, index): current = current.next |
And declare a variable, temp and point it to the next node of the current node.
| temp = current.next |
Link the new node, “Chicago” to the current.next node.
| current.next = Node(e) |
Finally, link the next node of the current.next to the temp, “Dallas” node.
| (current.next).next = temp |
d. removeFirst
When removing the first node in the current list, please follow this procedure:
If the list is empty, then return None which means nothing to remove.
| if self.__size == 0: return None |
If the list is not empty, declare a temporary variable, temp and assign it to the first node.
| temp = self.__head |
Move the head from the “Chicago” node to the “Atlanta” node.
| self.__head = self.__head.next |
Return temp.element, “Chicago”.
Once the first node is removed, if the head variable points to None, indicating an empty list, then the tail variable should also be set to None.
|
if self.__head == None: self.__tail = None |
e. removeLast
When removing the last node in the current list, please follow this procedure:
If the list is empty, then return None which means nothing to remove.
|
if self.__size == 0: |
If there is only one node in the list, declare a temporary variable, temp and assign it to the first node.
| temp = self.__head |
Then assign None to both the head and tail variables.
| self.__head = self.__tail = None |
If there are multiple nodes in the list, declare a variable named current and point it to the head node.
| current = self.__head |
Then iterate through the nodes using a loop, while moving to the previous node of the target node to be removed.
|
for i in range(self.__size - 2): current = current.next |
Declare a temporary variable named temp and assign it to the last node, which is "Dallas".
| temp = self.__tail |
Set the current node, "Macon", as the tail, and assign None to the tail 's next pointer (tail.next).
| self.__tail = current self.__tail.next = None |
Finally, return temp.element, “Dallas”.
f. removeAt(index)
When removing a node in the current list at the specified index, please follow this procedure:
If the index is out of range of the list, return None.
| if index < 0 or index >= self.__size: return None |
If the index is 0, it indicates that the first node is to be removed.
| elif index == 0: return self.removeFirst() |
If the index indicates the last node, remove the last node.
| elif index == self.__size -1: return self.removeLast() |
Otherwise, declare a temporary variable named previous and assign it to the head node, which is "Chicago".
Iterate through the nodes using a loop, while moving to the previous node of the target node to be removed.
Declare a temporary variable named current and assign it to the target node to be removed, which is "Macon".
Connect the previous.next to current.next.
Finally, return current.element, “Macon”.
4. Linked List Implementation
(Test Program)
Output:
|
(1) [Atlanta] (2) [Chicago, Atlanta] (3) [Chicago, Atlanta, Macon] (4) [Chicago, Atlanta, Macon, Dallas] (5) [Chicago, Atlanta, New York, Macon, Dallas] (6) [Chicago, Atlanta, New York, Macon, Dallas, Boston] (7) [LA, Chicago, Atlanta, New York, Macon, Dallas, Boston] (8) [Chicago, Atlanta, New York, Macon, Dallas, Boston] (9) [Chicago, Atlanta, Macon, Dallas, Boston] (10) [Chicago, Atlanta, Macon, Dallas] |