How do you create a linked list in python?

A linked list is a data structure made of a chain of node objects. Each node contains a value and a pointer to the next node in the chain.

Linked lists are preferred over arrays due to their dynamic size and ease of insertion and deletion properties.

The head pointer points to the first node, and the last element of the list points to null. When the list is empty, the head pointer points to null.

Linked lists in Python

Original Python does not ship with a built-in linked list data structure like the one seen in Java.

Let’s see how we can create our own implementation of a standard class-based singly linked list in Python.

1. Start with a single node

Let’s start with a single node since linking several nodes gives us a complete list. For this, we make a Node class that holds some data and a single pointer next, that will be used to point to the next Node type object in the Linked List.

# A single node of a singly linked list
class Node:
  # constructor
  def __init__(self, data, next=None): 
    self.data = data
    self.next = next

# Creating a single node
first = Node(3)
print(first.data)

2. Join nodes to get a linked list

The next step is to join multiple single nodes containing data using the next pointers, and have a single head pointer pointing to a complete instance of a Linked List.

Using the head pointer, we will be able to traverse the whole list, even perform all kinds of list manipulations while we are at it.

For this, we create a LinkedList class with a single head pointer:

# A single node of a singly linked list
class Node:
  # constructor
  def __init__(self, data = None, next=None): 
    self.data = data
    self.next = next

# A Linked List class with a single head node
class LinkedList:
  def __init__(self):  
    self.head = None

# Linked List with a single node
LL = LinkedList()
LL.head = Node(3)
print(LL.head.data)

3. Add required methods to the LinkedList class

Last but not least, we can add various linked list manipulation methods in our implementation.

Let’s have a look at the insertion and print methods for our LinkedList implementation below:

# A single node of a singly linked list
class Node:
  # constructor
  def __init__(self, data = None, next=None): 
    self.data = data
    self.next = next

# A Linked List class with a single head node
class LinkedList:
  def __init__(self):  
    self.head = None
  
  # insertion method for the linked list
  def insert(self, data):
    newNode = Node(data)
    if(self.head):
      current = self.head
      while(current.next):
        current = current.next
      current.next = newNode
    else:
      self.head = newNode
  
  # print method for the linked list
  def printLL(self):
    current = self.head
    while(current):
      print(current.data)
      current = current.next

# Singly Linked List with insertion and print methods
LL = LinkedList()
LL.insert(3)
LL.insert(4)
LL.insert(5)
LL.printLL()

RELATED TAGS

data structures

python

linked list

node

classes

Copyright ©2022 Educative, Inc. All rights reserved

Like arrays, Linked List is a linear data structure. Unlike arrays, linked list elements are not stored at a contiguous location; the elements are linked using pointers. They include a series of connected nodes. Here, each node stores the data and the address of the next node.

Linked-List

Why Linked List? 

Arrays can be used to store linear data of similar types, but arrays have the following limitations:

• The size of the arrays is fixed: So we must know the upper limit on the number of elements in advance. Also, generally, the allocated memory is equal to the upper limit irrespective of the usage. 
• Insertion of a new element / Deletion of a existing element in an array of elements is expensive: The room has to be created for the new elements and to create room existing elements have to be shifted but in Linked list if we have the head node then we can traverse to any node through it and insert new node at the required position.

Example: 
In a system, if we maintain a sorted list of IDs in an array id[] = [1000, 1010, 1050, 2000, 2040]. 
If we want to insert a new ID 1005, then to maintain the sorted order, we have to move all the elements after 1000 (excluding 1000). 

Deletion is also expensive with arrays until unless some special techniques are used. For example, to delete 1010 in id[], everything after 1010 has to be moved due to this so much work is being done which affects the efficiency of the code.

Advantages of Linked Lists over arrays:

• Dynamic Array.
• Ease of Insertion/Deletion.

Drawbacks of Linked Lists: 

• Random access is not allowed. We have to access elements sequentially starting from the first node(head node). So we cannot do a binary search with linked lists efficiently with its default implementation. 
• Extra memory space for a pointer is required with each element of the list. 
• Not cache friendly. Since array elements are contiguous locations, there is locality of reference which is not there in case of linked lists.

Types of Linked Lists:

• Simple Linked List – In this type of linked list, one can move or traverse the linked list in only one direction
• Doubly Linked List – In this type of linked list, one can move or traverse the linked list in both directions (Forward and Backward)
• Circular Linked List – In this type of linked list, the last node of the linked list contains the link of the first/head node of the linked list in its next pointer and the first/head node contains the link of the last node of the linked list in its prev pointer

Basic operations on Linked Lists:

• Deletion
• Insertion
• Search
• Display

Representation of Linked Lists: 

A linked list is represented by a pointer to the first node of the linked list. The first node is called the head of the linked list. If the linked list is empty, then the value of the head points to NULL. 

Each node in a list consists of at least two parts: 

• A Data Item (we can store integer, strings, or any type of data).
• Pointer (Or Reference) to the next node (connects one node to another) or An address of another node

In C, we can represent a node using structures. Below is an example of a linked list node with integer data. 
In Java or C#, LinkedList can be represented as a class and a Node as a separate class. The LinkedList class contains a reference of Node class type. 

C

struct Node {

    int data;

    struct Node* next;

};

C++

class Node {

public:

    int data;

    Node* next;

};

Java

class LinkedList {

    Node head;

    class Node {

        int data;

        Node next;

        Node(int d)

        {

            data = d;

            next = null;

        }

    }

}

Python

class Node:

    def __init__(self, data):

        self.data = data 

        self.next = None 

class LinkedList:

    def __init__(self):

        self.head = None

C#

class LinkedList {

    Node head;

    class Node {

        int data;

        Node next;

        Node(int d) { data = d; }

    }

}

Javascript

Construction of a simple linked list with 3 nodes:

C

#include

#include

struct Node {

    int data;

    struct Node* next;

};

int main()

{

    struct Node* head = NULL;

    struct Node* second = NULL;

    struct Node* third = NULL;

    head = (struct Node*)malloc(sizeof(struct Node));

    second = (struct Node*)malloc(sizeof(struct Node));

    third = (struct Node*)malloc(sizeof(struct Node));

    head->data = 1;

    head->next = second;

    second->data = 2;

    second->next = third;

    third->data = 3;

    third->next = NULL;

    return 0;

}

C++

#include

using namespace std;

class Node {

public:

    int data;

    Node* next;

};

int main()

{

    Node* head = NULL;

    Node* second = NULL;

    Node* third = NULL;

    head = new Node();

    second = new Node();

    third = new Node();

    head->data = 1;

    head->next = second;

    second->data = 2;

    second->next = third;

    third->data = 3;

    third->next = NULL;

    return 0;

}

Java

class LinkedList {

    Node head;

    static class Node {

        int data;

        Node next;

        Node(int d)

        {

            data = d;

            next = null;

        }

    }

    public static void main(String[] args)

    {

        LinkedList llist = new LinkedList();

        llist.head = new Node(1);

        Node second = new Node(2);

        Node third = new Node(3);

        llist.head.next = second;

        second.next

            = third;

    }

}

Python

class Node:

    def __init__(self, data):

        self.data = data 

        self.next = None 

class LinkedList:

    def __init__(self):

        self.head = None

if __name__ == '__main__':

    llist = LinkedList()

    llist.head = Node(1)

    second = Node(2)

    third = Node(3)

    llist.head.next = second 

    second.next = third 

C#

using System;

public class LinkedList {

    Node head;

    public class Node {

        public int data;

        public Node next;

        public Node(int d)

        {

            data = d;

            next = null;

        }

    }

    public static void Main(String[] args)

    {

        LinkedList llist = new LinkedList();

        llist.head = new Node(1);

        Node second = new Node(2);

        Node third = new Node(3);

        llist.head.next = second;

        second.next

            = third;

    }

}

Javascript

    var head;

     class Node {

        constructor(d)

        {

            this.data = d;

            this.next = null;

        }

    }

        var head = new Node(1);

        var second = new Node(2);

        var third = new Node(3);

        head.next = second;

        second.next = third;

Traversal of a Linked List

In the previous program, we created a simple linked list with three nodes. Let us traverse the created list and print the data of each node. For traversal, let us write a general-purpose function printList() that prints any given list.

We strongly recommend that you click here and practice it, before moving on to the solution.

C

#include

#include

struct Node {

    int data;

    struct Node* next;

};

void printList(struct Node* n)

{

    while (n != NULL) {

        printf(" %d ", n->data);

        n = n->next;

    }

}

int main()

{

    struct Node* head = NULL;

    struct Node* second = NULL;

    struct Node* third = NULL;

    head = (struct Node*)malloc(sizeof(struct Node));

    second = (struct Node*)malloc(sizeof(struct Node));

    third = (struct Node*)malloc(sizeof(struct Node));

    head->data = 1;

    head->next = second;

    second->data = 2;

    second->next = third;

    third->data = 3;

    third->next = NULL;

    printList(head);

    return 0;

}

C++

#include

using namespace std;

class Node {

public:

    int data;

    Node* next;

};

void printList(Node* n)

{

    while (n != NULL) {

        cout << n->data << " ";

        n = n->next;

    }

}

int main()

{

    Node* head = NULL;

    Node* second = NULL;

    Node* third = NULL;

    head = new Node();

    second = new Node();

    third = new Node();

    head->data = 1;

    head->next = second;

    second->data = 2;

    second->next = third;

    third->data = 3;

    third->next = NULL;

    printList(head);

    return 0;

}

Java

class LinkedList {

    Node head;

    static class Node {

        int data;

        Node next;

        Node(int d)

        {

            this.data = d;

            next = null;

        }

    }

    public void printList()

    {

        Node n = head;

        while (n != null) {

            System.out.print(n.data + " ");

            n = n.next;

        }

    }

    public static void main(String[] args)

    {

        LinkedList llist = new LinkedList();

        llist.head = new Node(1);

        Node second = new Node(2);

        Node third = new Node(3);

        llist.head.next = second;

        second.next

            = third;

        llist.printList();

    }

}

Python3

class Node:

    def __init__(self, data):

        self.data = data 

        self.next = None 

class LinkedList:

    def __init__(self):

        self.head = None

    def printList(self):

        temp = self.head

        while (temp):

            print(temp.data)

            temp = temp.next

if __name__ == '__main__':

    llist = LinkedList()

    llist.head = Node(1)

    second = Node(2)

    third = Node(3)

    llist.head.next = second 

    second.next = third 

    llist.printList()

C#

using System;

public class LinkedList {

    Node head;

    public class Node {

        public int data;

        public Node next;

        public Node(int d)

        {

            data = d;

            next = null;

        }

    }

    public void printList()

    {

        Node n = head;

        while (n != null) {

            Console.Write(n.data + " ");

            n = n.next;

        }

    }

    public static void Main(String[] args)

    {

        LinkedList llist = new LinkedList();

        llist.head = new Node(1);

        Node second = new Node(2);

        Node third = new Node(3);

        llist.head.next = second;

        second.next

            = third;

        llist.printList();

    }

}

Javascript

    var head;

    class Node {

        constructor(val) {

            this.data = val;

            this.next = null;

        }

    }

     function printList()

    {

        var n = head;

        while (n != null) {

            document.write(n.data + " ");

            n = n.next;

        }

    }

       var head = new Node(1);

        var second = new Node(2);

        var third = new Node(3);

        head.next = second;

        second.next = third;

        printList();

Time Complexity:

Auxiliary Space: O(N)

How do you create a linked list program in Python?

How do you create a simple linked list?

How do you create a linked list code?

How do you create a node in Python?