In this Lesson, we'll cover what linked lists are, how they work, the differences between singly and doubly linked lists, and examples and exercises to help solidify your understanding.

What is a Linked List?

A linked list is a linear data structure that consists of nodes, where each node contains a value and a pointer to the next (and sometimes previous) node. The first node is called the head, and the last node is called the tail.

Unlike arrays or lists, linked lists do not require contiguous memory allocation. They are dynamic and can be easily expanded or contracted during runtime.

Here's an example of a simple linked list:

head -> [1|*] -> [2|*] -> [3|null]

In this example, head is pointing to the first node [1|*], which contains a value of 1 and a pointer to the next node [2|*]. The second node contains a value of 2 and a pointer to the third node [3|null], which contains a value of 3 and a null pointer since it is the last node in the list.

Singly Linked Lists

There are two main types of linked lists: singly linked lists and doubly linked lists.

In a singly linked list, each node only contains a pointer to the next node in the list. This means that traversal can only occur in one direction.

Here's an example of a singly linked list:

head -> [1|*] -> [2|*] -> [3|null]

As mentioned earlier, the head points to the first node [1|*], which contains a value of 1 and a pointer to the second node [2|*]. The second node contains a value of 2 and a pointer to the third node [3|null]. The third node is the tail and contains a null pointer since there are no nodes after it in the list.

Doubly Linked Lists

In a doubly linked list, each node contains pointers to both the next and previous nodes in the list. This allows for traversal in both directions.

Here's an example of a doubly linked list:

head -> [1|null]<->[2]<->[3]<->null

In this example, the head points to the first node [1|null], which contains a value of 1 and null pointer to the previous node (since it's the head). The second node [2] contains a value of 2, a pointer to the previous node [1], and a pointer to the next node [3]. The third node [3] contains a value of 3, a pointer to the previous node [2], and a null pointer since it's the tail.

Common Linked List Operations

Now that we have a basic understanding of what linked lists are and how they work, let's go over some common operations that can be performed on them.

Insertion

Adding a new node to a linked list involves updating the pointers of the neighboring nodes appropriately. Here's an example of how to insert a node with a value of 4 at the end of a singly linked list:

new_node = Node(4)
current_node = head

while current_node.next:
    current_node = current_node.next
    
current_node.next = new_node

In this example, we first create a new node with a value of 4. We then set the current node to the head and traverse the list until we reach the last node. Once we're at the end, we update the next pointer of the last node to point to the new node.

Deletion

Removing a node from a linked list involves updating the pointers of the neighboring nodes appropriately as well. Here's an example of how to delete the node with a value of 2 from a doubly linked list:

head -> [1|null]<->[2]<->[3]<->null

current_node = head.next

while current_node:
    if current_node.value == 2:
        current_node.prev.next = current_node.next
        current_node.next.prev = current_node.prev
    current_node = current_node.next

In this example, we first set the current node to the second node in the list (since we want to delete the node with a value of 2). We then traverse the list until we find the node we want to delete. Once we find it, we update the next pointer of the previous node to point to the node after the one we want to delete, and the previous pointer of the next node to point to the node before the one we want to delete. This effectively removes the node from the list.

Traversal

Traversing a linked list involves visiting each node in the list and performing some operation on it (such as printing its value). Here's an example of how to traverse a singly linked list and print out each node's value:

current_node = head

while current_node:
    print(current_node.value)
    current_node = current_node.next

In this example, we first set the current node to the head of the list. We then loop through the list and print out the value of each node. After printing the value, we update the current node to be the next node in the list until we reach the end (which is when current_node will be None).

Examples and Exercises

Now that we know the basics of linked lists and some common operations, let's look at some examples and exercises to help solidify our understanding.

Example: Implementing a Singly Linked List

Here's an example implementation of a singly linked list in Python:

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None

    def add(self, value):
        new_node = Node(value)
        
        if not self.head:
            self.head = new_node
        else:
            current_node = self.head
            
            while current_node.next:
                current_node = current_node.next
                
            current_node.next = new_node
    
    def remove(self, value):
        if not self.head:
            return
        
        if self.head.value == value:
            self.head = self.head.next
        else:
            current_node = self.head
            
            while current_node.next:
                if current_node.next.value == value:
                    current_node.next = current_node.next.next
                    break
                
                current_node = current_node.next
    
    def traverse(self):
        current_node = self.head
        
        while current_node:
            print(current_node.value)
            current_node = current_node.next

In this implementation, we have a Node class that contains a value and a pointer to the next node. We also have a LinkedList class that contains a head pointer (which points to the first node in the list) and three methods: add, remove, and traverse.

The add method adds a new node with the given value to the end of the list. The remove method removes the first node found with the given value from the list. And the traverse method prints out the value of each node in the list.

Exercise: Implementing a Doubly Linked List

Your task is to implement a doubly linked list in Python. You should have a Node class that contains a value, a pointer to the previous node, and a pointer to the next node. You should also have a DoublyLinkedList class that contains a head pointer (which points to the first node in the list) and a tail pointer (which points to the last node in the list), and three methods: add, remove, and traverse.

The add method should add a new node with the given value to the end of the list. The remove method should remove the first node found with the given value from the list. And the traverse method should print out the value of each node in the list.

Hint: When adding or removing nodes, make sure to update the neighboring nodes' pointers appropriately.

Exercise: Reverse a Linked List

Your task is to write a function that takes a linked list as input and returns a new linked list with the nodes in the reverse order. For example, if the input linked list is [1|*] -> [2|*] -> [3|null], the output should be [3|*] -> [2|*] -> [1|null].

Hint: You can traverse the original linked list and add each node to the beginning of the new linked list (which effectively reverses the order).

Conclusion

Linked lists are an important data structure to understand in computer science. They are used in many real-world applications, such as representing songs in a playlist or navigating through a file system. By understanding how they work and how to perform common operations on them, you'll be better equipped to solve programming problems involving linked lists.