Native lesson simulator
Linked list traversal
Each node carries a value and a pointer to the next node.
Current pointer is on node 13; the next link moves one node forward.
Flash cards
Review the key moves
What is the main idea behind DSA Linked Lists Types?
Lesson checks
Practice each idea before moving on
Short Mimo-style checks built from this lesson's code, terms, and sequence.
Which statement best captures the main point of this lesson?
Complete the missing token from the example code.
___ __init__(self, data):Put the learning moves in the order that makes the concept easiest to apply.
Types of Linked Lists
There are three basic forms of linked lists:
- Singly linked lists
- Doubly linked lists
- Circular 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:
Note
What kind of linked list you need depends on the problem you are trying to solve.
Linked List Implementations
Below are basic implementations of
- Singly linked list
- Doubly linked list
- Circular singly linked list
- Circular doubly linked list
the next lesson will cover different operations that can be done on linked lists.
Singly Linked List Implementation
Below is an implementation of this singly linked list:
Example
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")Doubly Linked List Implementation
Below is an implementation of this doubly linked list:
Example
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")Circular Singly Linked List Implementation
Below is an implementation of this circular singly linked list:
Example
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: This makes the singly list circular.
Line 17: This is how the program knows when to stop so that it only goes through the list one time.
Circular Doubly Linked List Implementation
Below is an implementation of this circular doubly linked list:
Example
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: These links makes the doubly linked list circular.
Lines 26: This is how the program knows when to stop so that it only goes through the list one time.