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.