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.

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.

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.

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)

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

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

def __init__(self):

new_node = Node(value)

else:

while current_node.next:
current_node = current_node.next

current_node.next = new_node

def remove(self, value):
return

else:

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):

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.