---
title: "An Introduction to Linked List Data Structures | CoderPad"
description: "Linked lists are fundamental linear data structures alongside stacks, queues, arrays, and lists. Linked lists are used in web browsers, arithmetic operations, and board game implementation. Learn the linked list data structure and how to implement them in this blog post."
canonical: "https://coderpad.io/blog/development/an-introduction-to-linked-list-data-structures/"
last_modified: "2026-04-15 16:21:04"
---
[Back to blog](https://coderpad.io/blog/)

# An Introduction to Linked List Data Structures

November 2, 2022 12 Minute Read

By Abdulazeez Abdulazeez Adeshina

[Development](https://coderpad.io/blog/development/)

Linked lists are one of the fundamental [linear data structures](https://www.educative.io/answers/what-are-linear-data-structures) alongside stacks, queues, arrays, and lists.

A linked list is a continuous list of nodes where a node is a block structure housing the node value and a pointer (or memory) address to the next node. Each node from the head node has a`next`pointer that keeps the address of the next node till it gets to the last node, which points to nothing.

Linked lists are used in web browsers to keep track of web pages visited and moves in multi-player board games. Linked lists also find usage in implementing other linear data structures and graphs, dynamic memory allocation, and performing arithmetic operations on long integers.

The connection from one node to another node differentiates linked lists from a regular list or array. Unlike the linked lists, arrays don’t keep track of their next or other values.

Here is a visual representation of a linked list:

![A linked list with 4 nodes. Each node points to another node. The last node always points to NULL, except for circular linked lists.](https://coderpad.io/wp-content/uploads/2022/11/img_63626e083150c.png) A linked list with 4 nodes. Each node points to another node.The last node always points to NULL, except for circular linked lists.

Types of Linked Lists

The last node always points to NULL, except for circular linked lists.

## Types of Linked Lists

There are three types of linked lists:

1. Singly-linked list
2. Doubly linked list
3. Circular linked list

You can derive other linked lists from the basic ones, e.g., circular doubly linked lists. This article teaches you how to implement the singly and doubly linked list and briefly discusses the circular linked list.

>

💡 In this article, we’ll use the Python programming language for the implementations.

## Singly-linked list

You’re tasked with building a tool to retrieve documents connected to each other but stored at random memory locations. You’re puzzled as to what data structure to use to fit this use case, as arrays store documents sequentially. The good news is that you can use the singly linked list for this task.

A singly linked list is defined by its node. A singly linked list node has a value and the next pointer. The diagram below is an example of a singly linked list.

![A linked list with 4 nodes. Each node points to another node. The last node always points to NULL, except for circular linked lists.](https://coderpad.io/wp-content/uploads/2022/11/img_63626e083150c.png) A linked list with 4 nodes. Each node points to another node. The last node always points to NULL, except for circular linked lists.

To implement the linked list, start with the node class:

```
class Node:
    def __init__(self, value) -> None:
        self.value = value
        self.next = NoneCode language: Python (python)
```

In the code block above, the node class comprises two attributes:

- `value`: The value to be stored in the node.
- `next`: The pointer address to the next node. It has a default value of None ( NULL ).

Next, you need to implement the linked list class.

### The linked list class

The linked list class is a wrapper for adding methods for node operations, such as appending a node, prepending a node, and deleting a node. Let’s say you want to append a node to the middle of a long chain of nodes. Doing so manually would look like this:

```
nodes = Node(10)
nodes.next = Node(11)
nodes.next.next = Node(13)
nodes.next.next.next = Node(14)

# Insert a new node after 11.

new_node = Node(12)
new_node.next = nodes.next.next
nodes.next.next = new_nodeCode language: Python (python)
```

The process above is stressful. In a scenario where you need to perform this same operation for a couple of nodes, say 10, you have to do this manually every time. This operation brings forth unnecessary code bulkiness and complexity – known as space complexity. Having a linked list class with a method solves this all.

>

![ℹ️](https://coderpad.io/assets/emoji/2139.svg) Each new variable defined in a program takes a significant amount of space. For example, a node costs 48 bytes of space, and a thousand nodes will cost 48000 bytes. Each time the program is executed, this amount of space is used for a single node initialization operation ignoring the internal space used by the linked list methods. Not only does this extra space slow down your application, but it also impacts the planet via poor [eco-design](https://coderpad.io/blog/engineering-management/the-environmental-impact-of-digital-technology-and-how-software-eco-design-can-help/).

The linked list class is independent. The`LinkedList`class implementation is:

```
class LinkedList:
    def __init__(self) -> None:
        self.head = None
        self.tail = None
        Self.size = 0Code language: Python (python)
```

In the code block above, the linked list class comprises three attributes:

- `head`: The head of the linked list, which is the first node.
- `tail`: The tail of the linked list, which is the last node.
- `size`: The size of the linked list.

### Singly-linked list operations

The primary operations of a singly linked list include:

1. Traversal
2. Insertion
3. Deletion

To perform the operations mentioned above, you need to define the methods under the linked list class.

Before you begin to implement the primary operations, however, you will need to implement the`__len__`method in the`LinkedList`class to return the length of your linked list stored in the`self.size`variable:

```
def __len__(self) -> int:
   return self.sizeCode language: PHP (php)
```

With the`__len__`method implemented, you can return the size of the linked list with`len(linkedlist)`.

#### Traversal

In simple words, traversal is a process of accessing elements stored in an object. A traversal operation is executed to print the elements in a linked list.

Let’s implement our first method,`__str__`, to print out the elements in the linked list:

```
def __str__(self) -> str:
    linkedlist = ""
    current = self.head

    while current and current.next is not None:
        linkedlist += str(current.value) + "->"
        current = current.next

    linkedlist += str(current.value)
    return linkedlistCode language: Python (python)
```

The`__str__`method in Python returns the string representation of an object. This method returns the node values in your linked list as a string separated by`->`.

#### Insertion

The insertion operation enables you to add nodes to your linked list. You can add nodes to your linked list by prepending the node, appending the node, or by adding nodes at specific positions in the linked list.

Prepending a node

The prepend method adds a new node at the head of the linked list, making it the new head node. The previous head node is automatically set as the next node after the new node.

Implement the prepend method in the`LinkedList`class:

```
def prepend(self, element) -> None:
    new_node = Node(element)
    new_node.next = self.head

    self.head = new_node

    if self.tail == None:
        self.tail = self.head

    self.size += 1Code language: Python (python)
```

In the code block above, the`prepend`method takes an argument`element`, which is, in turn, passed to the`Node`class to form a node`new_node`. The`new_node`has its next pointer set to the head of the linked list`self.head`, and the linked list’s head node also points to the new node created.

The method then checks if the tail of the linked list does not exist; if the tail doesn’t exist, it is set to the value of the head node.

Lastly, the method increments the size of the linked list.

Appending a node

The`append`method adds a new node to the end of the linked list. This method traverses the linked list until the next node pointer points to`None`– signifying the end of the linked list. The new node is attached to the tail’s node pointer, and the size of the linked list is incremented.

Implement the method in the linked list class:

```
def append(self, element) -> None:
    node = self.head
    while node.next != None:
        node = node.next

    node.next = Node(element)
    self.tail = node.next
    self.size += 1Code language: Python (python)
```

Appending at a specific position

The last insertion operation is to append at a specific position. In this operation, a new node is added to the position specified. For example, if the linked list has four values, you can insert a new node at the third position. The node in the second position will have its next pointer pointing at the new node, and the new node points at the node originally in the third position.

In the`LinkedList`class, add the method:

```
def add_at_position(self, position, element) -> None:
    if position < 1 or position > self.size:
        raise IndexError("Position is invalid")

    if position == 1:
        self.prepend(element)
        return

    index = 1
    prev = None
    current = self.head
    new_node = Node(element)

    while index != position:
        index += 1
        prev = current
        current = current.next
    prev.next = new_node
    new_node.next = current
    self.size += 1Code language: Python (python)
```

With the insertion methods in place, create a new linked list and perform some operations:

```
ll = LinkedList()
ll.prepend(40)
ll.append(50)
ll.add_at_position(2, 45)

print(len(ll)) # 3
print(ll) # 40 -> 45 -> 50Code language: Python (python)
```

#### Deletion

The deletion operation involves removing a node from the linked list either from the head, tail or at a specified position. Implement the method for this operation in the`LinkedList`class:

```
def delete_node(self, position) -> None:
    if position < 1 or position > self.size:
        raise IndexError("Invalid position!")

    if position == 1:
        self.head = self.head.next
        return

    if position == self.size:
        prev = None
        current = self.head

        while current.next is not None:
            prev = current
            current = current.next

        prev.next = None
        self.tail = prev

        self.size -= 1
        return

   # Position specified isn't head nor tail.
     index = 1
     prev = None
     current = self.head

     while index != position:
         index += 1
         prev = current
         current = current.next

     prev.next = current.next

     self.size -= 1

     return current.elementCode language: Python (python)
```

In the code block above, the`delete_node`function performs three delete operations:

1. Deleting the head node: If the position specified is 1, the head node is deleted by setting the value of the head node to the second node in the linked list.
2. Deleting the tail node: If the position specified equals the number of nodes present in the linked list, the linked list is traversed to the end, and the second to the last node’s pointer is set to`None`to eliminate the tail node.
3. Deleting a different node: If the position doesn’t match the head or tail nodes, the linked list is traversed until the specified position is reached. The node preceding the node at the specified position will have its next pointer set to the node located after the deleted node.

All of the operations above decrease the size of the linked list. An`IndexError`will be returned if a wrong position is passed to the method.

If you delete the second node you created earlier, the new linked list will be:

```
ll.delete_node(2)
print(ll, len(ll)) # Prints 40 -> 50, 2Code language: Python (python)
```

## Doubly linked list

You’re tasked with implementing a new feature in a multiplayer board game (chess, checkers, tic-tac-toe, etc.) that enables a user to go back to their previous move. To implement this feature, you’ll likely need to use a doubly linked list data structure.

A doubly linked list has two node pointers—one pointer pointing to the previous node and the other pointing to the next node.

Here is a graphical representation:

A doubly linked list representation. Each node keeps a pointer to the previous and next node.

To implement a doubly linked list, implement the node class first:

```
class Node:
    def __init__(self, value):
        self.value = value
        self.previous = None
        self.next = NoneCode language: Python (python)
```

The`Node`class above comprises three attributes:

- `value`: The value to be stored in the node.
- `previous`: The pointer address of the previous node.
- `next`: The pointer address of the next node.

### The linked list class

The linked list class is a wrapper for adding methods for node operations. The`LinkedList`class definition for a doubly linked list is:

```
class LinkedList:
    def __init__(self) -> None:
        self.head = None
        self.tail = None
        self.size = 0Code language: Python (python)
```

### Doubly linked list operations

Just as before, the primary operations of a doubly linked list include:

1. Traversal
2. Insertion
3. Deletion

To perform the above-mentioned operations, you need to define the methods under the linked list class.

Before you begin to implement the primary operations, implement the`__len__`method in the`LinkedList`class to return the length of your linked list stored in the`self.size`variable:

```
def __len__(self) -> int:
       return self.sizeCode language: Python (python)
```

With the`__len__`method implemented, you can return the size of the linked list with`len(linkedlist)`.

This should look familiar, because it is the exact same method definition as a singly linked list.

#### Traversal

Let’s implement our first method,`__str__`, to print out the elements in the linked list:

```
def __str__(self) -> str:
    linkedlist = ""
    current = self.head

    while current and current.next is not None:
        linkedlist += str(current.value) + "<->"
        current = current.next

    linkedlist += str(current.value)
    return linkedlistCode language: Python (python)
```

In the code block above, the`__str__`method will iterate through the linked list and store each node value separated by the delimiter`<->`in a variable`linkedlist`which is returned when a linked list object is to be printed.

>

![ℹ️](https://coderpad.io/assets/emoji/2139.svg) The`__str__`and`__len__`methods are the same for all linked lists. The only difference is the delimiter`-`> for singly and`<->`for the doubly linked list.

#### Insertion

The insertion operation enables you to add nodes to your linked list either by prepending the node, appending the node, or adding the node at specific positions in the linked list.

Prepending a node

The`prepend`method adds a new node at the head of the linked list. Implement the prepend method in the`LinkedList`class:

```
def prepend(self, element) -> None:
    new_node = Node(element)
    new_node.next = self.head

    if self.head is not None:
        self.head.previous = new_node

    self.head = new_node

    if self.tail == None:
        self.tail = self.head

    self.size += 1Code language: Python (python)
```

In the code block above, the method starts by creating a new node,`new_node`, with the argument passed to the`prepend`method. The method assigns the next pointer to the head node. It then checks if the linked list is not empty and assigns the head node’s previous pointer to the new node.

Once the pointer assignments are complete, the new node is assigned as the new head of the linked list.

Appending a node

The`append`method adds a new node to the end of the linked list. This method traverses the linked list until the next node pointer points to`None`(the end of the linked list). Once the end of the linked list is reached, the new node is attached to the tail’s node pointer, and the size of the linked list is incremented.

Implement the method in the linked list class:

```
def append(self, element) -> None:
    if self.tail is None:
        self.prepend(element)
        return

    new_node = Node(element)

    self.tail.next = new_node

    new_node.previous = self.tail

    self.tail = new_node

    self.size += 1Code language: Python (python)
```

In the code block above, the`append`method checks if the tail of the linked list is`None`. If the tail is`None`, the method performs a prepend operation and exits.

However, if the tail exists, a new node is created and its previous pointer is set to the linked list tail node. The tail node as well sets its next pointer to the new node. Once the pointer assignment is completed, the new node is made the new tail by assigning the node to the`self.tail`variable.

Appending at a specific position

Linked list nodes can be appended at a specified position. An example is inserting a new node at the fourth position in a linked list with five values.

The node before the position specified will have its next pointer pointing at the new node and its next pointer pointing at the node originally at the position specified.

In the`LinkedList`class, add the method:

```
def add_at_position(self, position, element):
    if position < 1 or position > self.size:
        raise IndexError("Position is invalid")
    if position == 1:
        self.prepend(element)
        return

    index = 1
    current = self.head
    new_node = Node(element)

    while index != position:
        index += 1
        current = current.next

    prev = current.previous

    prev.next = new_node
    new_node.previous = prev
    new_node.next = current
    current.previous = new_node

    self.size += 1Code language: Python (python)
```

In the code block above, the method first checks if the position is valid before proceeding. If the position is invalid, the method returns an`IndexError`.

If the position specified is the head node position 1, the method invokes the`prepend`method for the insertion. Otherwise, the method traverses the whole linked list until it gets to the position and performs the following:

- The method assigns the preceding node’s next pointer to the new node
- Sets the new node’s previous pointer to the preceding node
- Sets the new node’s next pointer to the current node
- Sets the current node’s previous pointer to the new node

With the insertion methods in place, create a new linked list and perform some operations:

```
dll = LinkedList()
dll.prepend(40)
dll.prepend(30)
dll.append(50)
dll.add_at_position(1, 10)

print(dll) # 10<->30<->40<->50Code language: Python (python)
```

#### Deletion

The deletion operation removes a node from the linked list either from the head, tail or at a specified position. Implement the method for this operation in the`LinkedList`class:

```
def delete_node(self, position):
    if position < 1 or position > self.size:
        raise IndexError("Invalid position!")

    if position == 1:
        node_to_remove = self.head
        newHead = self.head.next
        node_to_remove.next = None
        node_to_remove.previous = None

        self.head = newHead
        self.size -= 1
        return node_to_remove.value

    if position == self.size:
        node_to_remove = self.tail
        new_tail = self.tail.previous

        node_to_remove.previous = None
        new_tail.next = None

        self.tail = new_tail
        self.size -= 1
        return node_to_remove.value
    index = 1
    current = self.head

    while index != position:
        index += 1
        current = current.next

    prev = current.previous
    prev.next = current.next
    current.next.previous = prev
    self.size -= 1
    return current.valueCode language: Python (python)
```

In the code block above, the`delete_node`function performs three delete operations:

1. Deleting the head node: If the position specified is 1, the head node is deleted by setting both pointers to`None`, and the second node is assigned the head node.
2. Deleting the tail node: If the position specified equals the number of nodes present in the linked list, the linked list is traversed to the end, and the second to the last node’s pointer is set to`None`to eliminate the tail node. The outgoing tail node’s pointers are also set to`None`respectively.
3. Deleting a different node: If the position doesn’t match the head or tail nodes, the linked list is traversed until the specified position is reached. For example, to delete the third node in a 5-value linked list, the second node will have its next pointer pointing to the fourth node, and the fourth node’s previous pointer will now point to the second node.The node preceding the node at the position will have its next pointer set to the node of the next pointer of the node to be deleted. The next pointer after the node to be deleted will have its previous pointer pointing to the node preceding the current node to be deleted.

All of the operations above decrease the size of the linked list. An`IndexError`will be returned if a wrong position is passed to the method.

If you delete the second node you created earlier, the new linked list will be:

```
dll.delete_node(2)

print(dll) # 10<->40<->50Code language: Python (python)
```

## Circular linked lists

Circular linked lists are singly linked lists except that their last node points to the first node as opposed to None. As a result, the circular linked list does not have a tail node. Circular linked lists are commonly used to manage computing resources.

The circular linked list’s last node’s next pointer is set to the first node’s address.

The circular linked list shares the same logic for insertion, traversal, and deletion as the singly linked list with the only difference being the assignment of the last node’s next pointer to the head node.

For example, the append method for the circular linked list is:

```

def prepend(self, value):
    cur = self.head
    new_node = Node(value)
    new_node.next = self.head

    if not self.head:
        new_node.next = new_node
    else:
        while cur.next != self.head:
            cur = cur.next
        cur.next = new_node
    self.head = new_nodeCode language: PHP (php)
```

In the code block above, the`prepend`method first checks if the head node is not present in the linked list. If there’s no head node, the new node’s next pointer is set to itself, creating a circle.
The circular linked list is implemented in the sandbox below to avoid repeating the implementation of the singular linked list.

## Try it out in the CoderPad sandbox!

In this article, you have learned what linked lists are and how to implement singly and doubly linked lists. You can play with the sandboxes beneath this section to test the method you learned as well as implement new methods – the [Coderpad Sandbox](https://app.coderpad.io) is an interactive sandbox for peer coding, live coding, and interviews.

Want more challenges? Create a sandbox and implement the reversal method for singly and doubly linked lists, create a tweet with your sandbox link, and tag [CoderPad](https://twitter.com/coderPad).

## Subscribe for more CoderPad insights

## Trending Articles

Previous slide Next slide [Development

## What is Prompt Engineering?

Introducing AI tools such as ChatGPT and Bard helps increase the efficiency of tasks such as data generation, code generation and completion, text summarization, etc. How were these AI tools trained to answer almost every question you ask them? The answer, prompt engineering, is discussed in this blog post.

Read the post](https://coderpad.io/blog/development/what-is-prompt-engineering/) [Development

## A Guide To Using React’s useCallback() Hook

Are you looking to optimize your React applications? Have you heard of the useCallback hook? useCallback is a powerful React hook that helps you optimize your application by preventing unnecessary re-renders. In this post, we'll dive into React's useCallback() hook, define referential equality and callback functions and how to tie it all together.

Read the post](https://coderpad.io/blog/development/a-guide-to-using-reacts-usecallback-hook/) [Development

## MySQL vs. PostgreSQL: How Do They Compare?

A database is a convenient tool that allows users to access information, maintain records, and apply commonly used operations, such as insertion, modification, deletion, and data organization. Learn about MySQL vs PostgreSQL, their features, advantages, and disadvantages. Finally, check out which one is the best choice for you.

Read the post](https://coderpad.io/blog/development/mysql-vs-postgresql-how-do-they-compare/) [Development

## PostgreSQL LIKE Operator: A Detailed Guide

When using databases, searching for values that match a given pattern is a familiar necessity. Learn how you can retrieve entries with queries including a particular string using Postgres LIKE operator.

Read the post](https://coderpad.io/blog/development/postgresql-like-operator-a-detailed-guide/) [Development

## How To Use DataProvider In TestNG With Examples

When it comes to testing there are many tools and techniques available. In this post, we'll discuss how to use DataProvider with TestNG.

Read the post](https://coderpad.io/blog/development/how-to-use-dataprovider-in-testng-with-examples/) [Development

## How To Get Up And Running With Django Migrations: A Guide

Django migrations are a way of handling the application of changes to a database schema. By following the steps outlined in this guide, you can easily set up and use migrations in your Django projects.

Read the post](https://coderpad.io/blog/development/how-to-get-up-and-running-with-django-migrations-a-guide/) [Development

## Writing A Parameterized Test In JUnit With Examples

A JUnit parameterized test allows you to decouple data from structure, generating cleaner and more reliable tests. Learn more in this guide.

Read the post](https://coderpad.io/blog/development/writing-a-parameterized-test-in-junit-with-examples/) [Development

## How To Use Assert In JUnit With Examples

The JUnit Assert class is what you use to write unit testing assertions in JUnit. Learn more about it in this guide, full of examples.

Read the post](https://coderpad.io/blog/development/how-to-use-assert-in-junit-with-examples/) [Development

## A Simple Guide To TypeORM: What It Is And How To Use It

Considering current languages have object-oriented programming features, most database management systems are based on the relational model, with tables instead of objects. For these reasons, mapping relational objects is very important in development. In this article, you will learn what TypeORM, one of the main tools used today, is.

Read the post](https://coderpad.io/blog/development/a-simple-guide-to-typeorm-what-it-is-and-how-to-use-it/) [Development

## Using PreparedStatement in JDBC With Examples

In this post, we'll see why and how to work with JDBC and PreparedStatement. We will also learn along with examples using code.

Read the post](https://coderpad.io/blog/development/using-preparedstatement-in-jdbc-with-examples/) [Development

## React vs React Native: The Differences Explained

React and React Native are similar in that they both allow web developers to build applications based on the unique concept of components. But the two frameworks do this in radically different ways. In this post, we cover the key differences between react and react native frameworks, implementation, and which is an appropriate choice.

Read the post](https://coderpad.io/blog/development/react-vs-react-native-the-differences-explained/) [Development

## Logging in Django

The most challenging part of fixing a problem is identifying it. Unfortunately, this statement is exceptionally true when it comes to debugging. Learn how to use the power of logging into your Django applications to improve your debug process in this article.

Read the post](https://coderpad.io/blog/development/logging-in-django/)

## Hire with confidence.

See why engineering teams trust CoderPad to evaluate developers with realistic, AI-ready hiring workflows.

[Request a demo](https://coderpad.io/sales/)