DSA Linked Lists Types
Types of Linked Lists
Three fundamental types of linked lists exist:
1.Singly linked lists
2.Doubly linked lists
3.Circular linked lists
The most basic type of linked list is a singly linked list. Because each node, as seen in the graphic below, has only one address to the next node, it requires less memory space.
A doubly linked list requires additional memory because, as seen in the illustration below, each node carries an address to both the node before it and the node after it. However, if you want to be able to navigate both up and down the list, doubly linked lists are useful.
A circular linked list is like a singly or doubly linked list with the first node, the “head”, and the last node, the “tail”, connected.
In singly or doubly linked lists, we can find the start and end of a list by just checking if the links are null. But for circular linked lists, more complex code is needed to explicitly check for start and end nodes in certain applications.
Circular linked lists are good for lists you need to cycle through continuously.
The image below is an example of a singly circular linked list:
An illustration of a double circular linked list may be found below:
Note: Depending on the issue you’re attempting to solve, a linked list of different kinds may be required.
Linked List Implementations
Here are some basic examples of how to:
1.Singly linked list
2.Doubly linked list
3.Circular singly linked list
4.Circular doubly linked list
The various operations that can be performed on linked lists are covered on the next page.
1. Singly Linked List Implementation
An example of this singly linked list in action is shown below:
Example
A simple Python singly linked list:
(This is the same example as on the bottom of the previous page.)
class Node:
def __init__(self, data):
self.data = data
self.next = None
node1 = Node(3)
node2 = Node(5)
node3 = Node(13)
node4 = Node(2)
node1.next = node2
node2.next = node3
node3.next = node4
currentNode = node1
while currentNode:
print(currentNode.data, end=" -> ")
currentNode = currentNode.next
print("null")
2. Doubly Linked List Implementation
An example of this doubly linked list in action is shown below:
Example
A simple Python doubly linked list:
class Node:
def __init__(self, data):
self.data = data
self.next = None
self.prev = None
node1 = Node(3)
node2 = Node(5)
node3 = Node(13)
node4 = Node(2)
node1.next = node2
node2.prev = node1
node2.next = node3
node3.prev = node2
node3.next = node4
node4.prev = node3
print("\nTraversing forward:")
currentNode = node1
while currentNode:
print(currentNode.data, end=" -> ")
currentNode = currentNode.next
print("null")
print("\nTraversing backward:")
currentNode = node4
while currentNode:
print(currentNode.data, end=" -> ")
currentNode = currentNode.prev
print("null")
3. Circular Singly Linked List Implementation
An example of this circular singly linked list in action is shown below:
Example
A basic circular singly linked list in Python:
class Node:
def __init__(self, data):
self.data = data
self.next = None
node1 = Node(3)
node2 = Node(5)
node3 = Node(13)
node4 = Node(2)
node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node1
currentNode = node1
startNode = node1
print(currentNode.data, end=" -> ")
currentNode = currentNode.next
while currentNode != startNode:
print(currentNode.data, end=" -> ")
currentNode = currentNode.next
print("...")
Line 14: The singly list becomes circular as a result.
Line 17: The software uses this information to determine when to end its one-time run over the list.
4. Circular Doubly Linked List Implementation
An example of this circular double linked list in action is shown below:
Example
A simple Python circular doubly linked list:
class Node:
def __init__(self, data):
self.data = data
self.next = None
self.prev = None
node1 = Node(3)
node2 = Node(5)
node3 = Node(13)
node4 = Node(2)
node1.next = node2
node1.prev = node4
node2.prev = node1
node2.next = node3
node3.prev = node2
node3.next = node4
node4.prev = node3
node4.next = node1
print("\nTraversing forward:")
currentNode = node1
startNode = node1
print(currentNode.data, end=" -> ")
currentNode = currentNode.next
while currentNode != startNode:
print(currentNode.data, end=" -> ")
currentNode = currentNode.next
print("...")
print("\nTraversing backward:")
currentNode = node4
startNode = node4
print(currentNode.data, end=" -> ")
currentNode = currentNode.prev
while currentNode != startNode:
print(currentNode.data, end=" -> ")
currentNode = currentNode.prev
print("...")
Lines 13 and 22: The double linked list is circularized thanks to these linkages.
Line 26: This is how the software determines when to end its one-time run over the list.
