Loading lesson path
Concept visual
Start at both ends
There are three basic forms of linked lists:
A singly linked list is the simplest kind of linked lists. It takes up less space in memory because each node has only one address to the next node, like in the image below. A doubly linked list has nodes with addresses to both the previous and the next node, like in the image below, and therefore takes up more memory. But doubly linked lists are good if you want to be able to move both up and down in the list. 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: The image below is an example of a doubly circular linked list:
What kind of linked list you need depends on the problem you are trying to solve.
The next page will cover different operations that can be done on linked lists.
A basic singly linked list in Python: (This is the same example as on the bottom of the previous page.) class Node:
def __init__(self, data):Formula
self.data = data self.next = NoneFormula
node1 = Node(3)
node2 = Node(5)
node3 = Node(13)
node4 = Node(2)Formula
node1.next = node2 node2.next = node3 node3.next = node4Formula
currentNode = node1 while currentNode:print(currentNode.data, end=" -> ")
currentNode = currentNode.next print("null")A basic doubly linked list in Python: class Node:
def __init__(self, data):Formula
self.data = data self.next = None self.prev = NoneFormula
node1 = Node(3)
node2 = Node(5)
node3 = Node(13)
node4 = Node(2)Formula
node1.next = node2Formula
node2.prev = node1 node2.next = node3Formula
node3.prev = node2 node3.next = node4Formula
node4.prev = node3print("\nTraversing forward:")Formula
currentNode = node1 while currentNode:print(currentNode.data, end=" -> ")
currentNode = currentNode.next print("null")print("\nTraversing backward:")Formula
currentNode = node4 while currentNode:print(currentNode.data, end=" -> ")
currentNode = currentNode.prev print("null")A basic circular singly linked list in Python: class Node:
def __init__(self, data):Formula
self.data = data self.next = NoneFormula
node1 = Node(3)
node2 = Node(5)
node3 = Node(13)
node4 = Node(2)Formula
node1.next = node2 node2.next = node3 node3.next = node4 node4.next = node1currentNode = node1 startNode = node1 print(currentNode.data, end=" -> ")Formula
currentNode = currentNode.nextwhile currentNode != startNode:
print(currentNode.data, end=" -> ")Formula
currentNode = currentNode.nextprint("...")This makes the singly list circular.
This is how the program knows when to stop so that it only goes through the list one time.
A basic circular doubly linked list in Python: class Node:
def __init__(self, data):Formula
self.data = data self.next = None self.prev = NoneFormula
node1 = Node(3)
node2 = Node(5)
node3 = Node(13)
node4 = Node(2)Formula
node1.next = node2 node1.prev = node4Formula
node2.prev = node1 node2.next = node3Formula
node3.prev = node2 node3.next = node4Formula
node4.prev = node3 node4.next = node1print("\nTraversing forward:")
currentNode = node1 startNode = node1 print(currentNode.data, end=" -> ")Formula
currentNode = currentNode.nextwhile currentNode != startNode:
print(currentNode.data, end=" -> ")
currentNode = currentNode.next print("...")print("\nTraversing backward:")
currentNode = node4 startNode = node4 print(currentNode.data, end=" -> ")Formula
currentNode = currentNode.prevwhile currentNode != startNode:
print(currentNode.data, end=" -> ")
currentNode = currentNode.prev print("...")These links makes the doubly linked list circular.
This is how the program knows when to stop so that it only goes through the list one time.
Take a look at this singly Linked List: How can we make this Linked List circular? The list can be made circular by connecting the next pointer in the last node, to the node. Submit Answer »