Data Structures: Linked Lists
Tags: beginners, computerscience, algorithms, theory
Published: 2021-02-28 04:23:33

How to reverse a linked list?

You probably heard this question a billion times already, may it be from coding interviews, colleagues, and even some YouTube influencers saying you aint a programmer if you don't know how to reverse a linked list (talking to you TechLead). 

No worries, there's no shame in not knowing that. 

However, it is my duty as your data structures teacher, to teach you that and pass on knowledge from one programmer to another. 

So without further ado, let's master the **linked list**.

## Table of Contents

- [Demystifying Linked Lists](#1)
- [Where the hell are they used?](#2)
- [Types of Linked Lists](#3)
- [Complexity](#4)
- [Implementations of Linked Lists](#5)
- [How to reverse a god damn linked list?](#6)
- [Conclusion](#7)
- [Additional Resources](#8)

## Demystifying Linked Lists <a name="1"></a>

When I first started studying data structures, I was pretty terrified of linked lists. 

I don't know what it is, but it sounds so complicated. 

But boy was I wrong. 

It's actually far simpler than I thought. 

So to begin with, let us define the linked list.

- A linked list is a **data structure**.
- It's **linear**, meaning elements are in a sequence (ex. 1 2 3 4 5).
- Elements of a linked list are **NOT** stored sequentially to each other in memory(RAM).
- Elements are **linked** to each other's using **pointers**.

Below is an image visualizing linked lists:

<figure>
  <img src="https://dev-to-uploads.s3.amazonaws.com/uploads/articles/yq76y3oe20igao7dvy1g.jpg">
  <figcaption>https://beginnersbook.com/2013/12/linkedlist-in-java-with-example/</figcaption>
</figure>

Let us break this image down: 

1. **Head**: The first element of a linked list (in this case it is the element at memory address 3200)
2. **Content**: Your data (can be anything you'd want ex. string, ints, floats, etc...)
3. **Pointer**: Address in memory to the next element (node).
4. **Tail**: Last element of a linked list (you can identify a tail by it having always a pointer of next element to null)

## Where the hell are they used? <a name="2"></a>

As programmers, our first instinct is to see how we can use this in our current or new projects, and this is valid thinking. 

We don't wanna be studying something that we might never use.

Right?

Well, that is why I've compiled down a list of use-cases for linked lists.

- Implementation of Stacks and Queues (FIFO)
- Implementation of Graphs
- Dynamic memory allocation
- Maintaining directory of names
- Performing arithmetic operations on long integers
- Manipulation of Polynomials
- Representing sparse matrices

## Types of Linked Lists <a name="3"></a>

There are three types of linked lists:

### Single Linked List

A singly linked list is a type of linked list that is unidirectional, that is, it can be traversed in only one direction from head to the last node(tail).

<figure>
  <img src="https://dev-to-uploads.s3.amazonaws.com/uploads/articles/2iy0ne1jodh53ldccu3w.png">
  <figcaption>Single Linked List</figcaption>
</figure>

### Doubly Linked List

A doubly linked list is a type of linked list that is bidirectional, that is, it can be traversed in two directions, from head to the last node(tail) and vice-versa.

<figure>
  <img src="https://dev-to-uploads.s3.amazonaws.com/uploads/articles/pdg97dkr5wy47f1x7pwz.png">
  <figcaption>Doubly Linked List</figcaption>
</figure>

### Circular Linked List

A circular linked list is a type of linked list, in which the head points to the tail, and the tail points to the head. Both Singly Linked List and Doubly Linked List can be made into a circular linked list.

<figure>
  <img src="https://dev-to-uploads.s3.amazonaws.com/uploads/articles/nzft6pr4k98si4kb7s65.png">
  <figcaption>Singly Circular Linked List</figcaption>
</figure>

<figure>
  <img src="https://dev-to-uploads.s3.amazonaws.com/uploads/articles/o8o7krq5xhhp5e2evyqy.png">
  <figcaption>Doubly Circular Linked List</figcaption>
</figure>

## Complexity <a name="4"></a>

Keep in mind when measuring the complexity of a data structure, we always look at the worst-case scenario. So we can imagine that the size of this linked list is in the millions or even billions.

### Access

Both single and doubly linked list has to traverse the whole linked list to find the specific element that we are searching for. That is why the complexity for is  O(n).

### Search

Search is similar to access time, so it is also O(n).

### Insertion

Linked lists are used best in insertion and deletion due to the elements not needing to be explicitly sequential in memory. 

Insertion is pretty simple. 

For example, if you want to add an element to the beginning of a linked list(head). You simply create the element in some memory location and you point it to the previous head. This is why the time complexity is O(1).

<figure>
  <img src="https://dev-to-uploads.s3.amazonaws.com/uploads/articles/016ipeej19gvrk6vz4q5.png">
  <figcaption>Insertion in the middle of the list</figcaption>
</figure>

### Deletion

Similar to insertion, the time complexity is O(1), because to delete your not gonna have to go through the whole list, shifting elements. You simply manipulate the pointers of the previous and next element that you want to delete.

<figure>
  <img src="https://dev-to-uploads.s3.amazonaws.com/uploads/articles/cfkdmq6wnkmapuv9uqr0.png">
  <figcaption>Deletion in Linked List</figcaption>
</figure>

## Implementation of Linked List <a name="5"></a>

Usually, to represent a node in a linked list, we create a class with these properties:

```python
class Node:
    def __init__(self, data=None):
        self.data = data
        self.nextval = None
```

- **Data**: value of the data (string, int, etc...).
- **Nextval**: pointer or reference to the next element in the list.

The standard linked list interface requires us to implement these methods:

1. `list` - Display all elements/nodes.
2. `push` - insert at the end of the list.
3. `insertAtBeginning` - insert at the beginning of the list 
4. `insert` - inserting in between two Data Nodes
5. `remove` - remove an existing node using the key for that node

Our base class will look like this: 

```python
class SLinkedList: # Single Linked List
    def __init__(self):
        self.headval = None 
```

Let's implement the methods one by one.

### Display all elements

```python
class SLinkedList:
    def __init__(self):
        self.headval = None

    def list(self):
        printval = self.headval
        while printval is not None:
            print (printval.dataval)
            printval = printval.nextval
```

### Insert at the beginning of the list

```python
class SLinkedList:
    def __init__(self):
        self.headval = None

    def insertAtBeginning(self,newdata):
        NewNode = Node(newdata)

	# Update the new nodes next val to existing node
        NewNode.nextval = self.headval
        self.headval = NewNode
```

### Insert at the end of the list

```python
class SLinkedList:
    def __init__(self):
        self.headval = None

   # Function to add newnode
    def push(self, newdata):
        NewNode = Node(newdata)
        if self.headval is None:
            self.headval = NewNode
            return
        laste = self.headval
        while(laste.nextval):
            laste = laste.nextval
        laste.nextval=NewNode
```

### Insert between two nodes

```python
class SLinkedList:
    def __init__(self):
        self.headval = None

    def insertBetween(self,middle_node,newdata):
        if middle_node is None:
            print("The mentioned node is absent")
            return

        NewNode = Node(newdata)
        NewNode.nextval = middle_node.nextval
        middle_node.nextval = NewNode
```

### Remove a node using it's key

```python
class SLinkedList:
    def __init__(self):
        self.head = None
		
    def remove(self, Removekey):

        HeadVal = self.head

        if (HeadVal is not None):
            if (HeadVal.data == Removekey):
                self.head = HeadVal.next
                HeadVal = None
                return

        while (HeadVal is not None):
            if HeadVal.data == Removekey:
                break
            prev = HeadVal
            HeadVal = HeadVal.next

        if (HeadVal == None):
            return

        prev.next = HeadVal.next

        HeadVal = None
```

Keep in mind, here we are implementing a single-linked list. Implementing a double-linked list is similar, apart from the extra `prev` variable which will store the pointer or reference to the previous element. It will look something like this.

```python
class Node:
    def __init__(self, data=None):
        self.data = data
        self.next = None
	self.prev = None
```

## How to reverse a god damn linked list? <a name="6"></a>

Congratulations, you know about linked lists.

Now, coming back to our main question. 

How do we reverse a linked list?

Think about it, and then proceed to read the answer below.

To help you imagine this:

Input: 1→ 2→ 3→ 4

Output: 4 → 3 → 2 → 1

---

---

---

---

---

---

---

---

---

### Solution

There are multiple ways to reverse a linked list, which includes:

- Iterative Method
- Recursive Method
- Stack Method

For the sake of simplicity, we are going to use the iterative method. 

Pseudocode:

1. Initialize three pointers `prev` as NULL, `curr` as head and `next` as NULL.
2. Iterate through the linked list. In the loop, do the following:

```php
// Before changing next of current, 
// store next node 
next = curr->next
// Now change next of current 
// This is where actual reversing happens 
curr->next = prev 
// Move prev and curr one step forward 
prev = curr 
curr = next
```

<figure>
  <img src="https://dev-to-uploads.s3.amazonaws.com/uploads/articles/5bz6xfjj3mrwgia9vnhz.gif">
  <figcaption>GeeksForGeeks</figcaption>
</figure>

### Python Implementation

```python
# Python program to reverse a linked list
# Time Complexity: O(n)
# Space Complexity: O(1)

# Node class

class Node:

	# Constructor to initialize the node object
	def __init__(self, data):
		self.data = data
		self.next = None

class LinkedList:

	# Function to initialize head
	def __init__(self):
		self.head = None

	# Function to reverse the linked list
	def reverse(self):
		prev = None
		current = self.head
		while(current is not None):
			next = current.next
			current.next = prev
			prev = current
			current = next
		self.head = prev

	# Function to insert a new node at the beginning
	def push(self, new_data):
		new_node = Node(new_data)
		new_node.next = self.head
		self.head = new_node

	# Utility function to print the linked LinkedList
	def printList(self):
		temp = self.head
		while(temp):
			print temp.data,
			temp = temp.next

# Driver code
llist = LinkedList()
llist.push(20)
llist.push(4)
llist.push(15)
llist.push(85)

print "Given Linked List"
llist.printList()
llist.reverse()
print "\nReversed Linked List"
llist.printList()

# This code is contributed by Nikhil Kumar Singh(nickzuck_007)
```

## Conclusion <a name="7"></a>

In summary today we learned:

1. Linked Lists and their properties.
2. Where it is used
3. Implementation
4. How to reverse one

I hope you learned something today, and if you got any questions/suggestions feel free to comment them down in the description.

## Additional References <a name="8"></a>

- [https://www.geeksforgeeks.org/reverse-a-linked-list/](https://www.geeksforgeeks.org/reverse-a-linked-list/)
- [https://www.geeksforgeeks.org/data-structures/linked-list/](https://www.geeksforgeeks.org/data-structures/linked-list/)