logo codesdope

Linked Lists


So far, we know that a data structure is a way to keep our data, and a linked list is the first data structure we are going to study in this course. Breaking the name "Linked List", it is a list of elements (containing data) in which the elements are linked together.

linked list

As you can see in the above picture, each data is connected (or linked) to a different data and thus, forming a linear list of data, and this is a linked list. Since data in a linked list are stored in a linear fashion, a linked list is a linear data structure. There are also non-linear data structures like trees, graphs, etc. which we are going to study further in this course.

Till now, you know that we have to connect data of a linked list and to do so, we put our data in nodes and these nodes are connected in the desired fashion.

node

So before going further, let's discuss about nodes.



Node


A node can be viewed as a container or a box which contains data and other information in it. Nodes are connected (or organized) in a specific way to make data structures like linked lists, trees, etc.

linked list using nodes

In the above picture, each node has two parts, one stores the data and another is connected to a different node. The last node is not connected to any other node and thus, its connection to the next node is null.

In a linked list, a node is connected to a different node forming a chain of nodes.

linked list

Thus to make a linked list, we first need to make a node which should store some data into it and also a link to another node.

a node

There can be different ways to make this node in different languages, we are going to discuss the making of the node in C, Java and Python.

C


As discussed above, our node should store some data and a connection to a different node. We will use structure to store this information, and to store the connection, we can simply store the address of the node which it will be linked to.

node using structure in C

struct node {
  int data;
  struct node *next;
};

So, we have made a structure named node which stores an integer named data and a pointer named next to another structure (node).

connecting nodes

Let’s use this structure to make two nodes and connect one with another.

#include <stdio.h>
#include <stdlib.h>

struct node {
    int data;
    struct node *next;
};

int main() {
    struct node *a, *b;
    a = malloc(sizeof(struct node));
    b = malloc(sizeof(struct node));

    a->data = 10;
    b->data = 20;

    a->next = b;
    b->next = NULL;

    printf("%d\n%d\n",a->data, a->next->data);
    return 0;
}

struct node *a, *b;
a = malloc(sizeof(struct node));
b = malloc(sizeof(struct node));

Here, we are making two nodes (structure named node) and allocating space to them using the malloc function.

a->data = 10;
b->data = 20;

And then we are setting the values of data of the nodes a and b.

a->next = b;
b->next = NULL;

linked list in C

We are storing the address of b in the next variable of a. Thus, next of a is now storing the address of b or we can say the next of a is pointing to b.

Since there is no node for the next of b, so we are making next of b null.

Java


class Node {
  public int data;
  public Node next;
}

You can see that we have created a class named Node to represent a node and the class has two members - the first is the data (an integer) which our node is going to store and the other is another node which is the next node.

node in java

As we have created our class which meets our requirement of a node, let’s create two objects of this Node class and connect the next of the first node with the second one.

class Node {
  public int data;
  public Node next;

  public Node(int d) {
    data = d;
  }
}

class List {
  public static void main(String[] args) {
    Node a, b;
    a = new Node(10);
    b = new Node(20);

    a.next = b;
    b.next = null;

    System.out.print(a.data+"\n"+a.next.data+"\n");
  }
}

Node a, b; → Here, we are creating two nodes (or two objects of the Node class).

a.next = b; → We are storing b in next of a. So, next of a is now linked to the node b.

Since b is the last node (there is no node to point next of b to), we are making next of b null - b.next = null;.

Python


class Node():
    def __init__(self, data):
        self.data = data

a = Node(10)
b = Node(20)

a.next = b
b.next = None

print(a.data)
print(a.next.data)

Here, we have created a class named Node to represent a node. 'data' is used to store the data of the node.

a = Node(10)
b = Node(20)

We have created two nodes a and b with data 10 and 20 respectively and then we are making b the next of a using a.next = b. Since there is no other node to make it next of b, we are making next of b None.

linked list in python


Now we know how to create nodes and use them. We also know how to connect a node with a different node, so let’s move ahead and learn about linked lists.

Making and Traversing a Linked List


In the above examples, we have made two nodes a and b and we were able to access the node b with a.next. Suppose there are few more nodes, we can easily access them if we have access to the first node. This is explained in the picture given below.

head of linked list

Generally, we call the first node of a linked list the "head" of the linked list, and we always keep the access of the head of the linked list so that we have access to all the nodes of a linked list.

Traversing a Linked List


Traversing is visiting all the nodes of a linked list. As stated above, we always keep a record of the head of a linked list. We also know that the last node of a linked list is null.

linked list

So, we start a loop from the head of the linked list and end it when the node is null.

traversing linked list

Let's make a function to traverse over all the nodes of a linked list. We will pass the linked list (L) to it - TRAVERSE(L).

Now, we make a temporary pointer and point it to the head of the linked list (L) - temp = L.head.

We have a pointer pointing to the head of the linked list, thus we can start a loop and end it when this pointer will point to null (last element) i.e., while(temp != null).

At the end of each iteration, we have to just point the temp pointer to the next of the node i.e., temp = temp.next.

TRAVERSE(L)
    temp = L.head
    while(temp != null)
        temp = temp.next

So, temp = temp.next will make the temp point the next node in each iteration and the loop will run until the last node (until temp is not null).

code for traversing linked list

Till now, we know what a linked list is, what a node is and how to traverse over each node of a linked list. Let's learn about adding nodes to a linked list so that we can make a linked list.

Inserting Nodes in a Linked List


There can be three different positions where we can insert a new node in a linked list:

  • At the beginning of the list.
  • At the end of the list.
  • Anywhere except the above-mentioned positions.

Inserting a New Node at the Beginning of a Linked List


We start by passing the node (n) and the linked list (L) to a function i.e., INSERT_AT_BEGINNING(L, n).

adding node at beginning of linked list

After this, we point the next of the node to the head of the linked list - n.next = L.head.

joining new node to linked list

Since the head should always point to the first element of the linked list, so we change the head to point to the new node n i.e, L.head = n.

changing head of the linked list

INSERT_AT_BEGINNING(L, n)
    n.next = L.head
    L.head = n

Inserting a New Node at the End of a Linked List.


To insert a node at the end of a linked list, we just iterate to the last of the linked list and add a new node there. This is described in the picture given below.

adding new node to last of linked list

We start by passing the linked list and the node to the function - INSERT_AT_LAST(L, n).

Our next task is to iterate to the last of the linked list.

temp = L.head
while(temp.next != null)
    temp = temp.next

After this, we just need to add the node there.

INSERT_AT_LAST(L, n)
    temp = L.head
    while(temp.next != null)
        temp = temp.next

    temp.next = n

Inserting a New Node in the Middle of a Linked List


To insert a new node in the middle of a linked list, we need to break the existing links and create new links. This will be clear from the picture given below.

adding a node in middle of a linked list

So, we start by passing the node to be inserted (n) and the node after which we are going to insert this node (a) i.e., INSERT_NODE_AFTER(n, a).

We point next of the new node (n) to next of the node a.

linking new node to linked list

n.next = a.next

After this, we point next of the a to the new node.

inserting node in middle of a linked list

a.next = n

inserting node in middle of a linked list

INSERT_NODE_AFTER(n, a)
    n.next = a.next
    a.next = n

Now, we are able to create a linked list and also add nodes to it. Let’s complete this chapter by learning to delete a node from a linked list.

Deleting a Node from a Linked List


We delete any node of a linked list by connecting the predecessor node of the node to be deleted by the successor node of the node. For example, if we have a linked list a → b → c, then to delete the node 'b', we will connect 'a' to 'c' i.e., a → c. But this will make the node 'b' inaccessible and this type of inaccessible nodes are called garbage.

We might need to clean this garbage ourself in some languages like C by using the free function while some languages like Java does it automatically. In the pseudocode, we will assume that a language does it automatically. However, you can see the full code in C, Java and Python at the end of this chapter.

DEL(L, n)
    tmp = L.head
    if tmp == n // node to be deleted is head
        L.head = n.next

    else // node to be deleted is not head
        while(tmp != null)
            if tmp.next == n
                tmp.next = n.next //linking
                break
            tmp = tmp.next

We will first iterate to the node previous to the node n. So, we will first start from the head of the linked list - tmp = L.head.

If the node we are going to delete is the head of the linked list (if tmp == n), then we will just update the head pointer - L.head = n.next.

deleting head from a linked list

Otherwise, we will iterate to the node previous to the node n - if tmp.next == n and then link the node previous of the node to be deleted to the next of it (tmp.next = n.next).

deleting node from a linked list

  • C
  • Python
  • Java
#include <stdio.h>
#include <stdlib.h>

typedef struct node {
  int data;
  struct node *next;
}node;

typedef struct linked_list {
  struct node *head;
}linked_list;

//to make new node
node* new_node(int data) {
  node *z;
  z = malloc(sizeof(struct node));
  z->data = data;
  z->next = NULL;

  return z;
}

//to make a new linked list
linked_list* new_linked_list(int data) {
  node *a; //new node for head of linked list
  a = new_node(data);

  linked_list *l = malloc(sizeof(linked_list)); //linked list
  l->head = a;

  return l;
}

void traversal(linked_list *l) {
  node *temp = l->head; //temporary pointer to point to head

  while(temp != NULL) { //iterating over linked list
    printf("%d\t", temp->data);
    temp = temp->next;
  }

  printf("\n");
}

//new node before head
void insert_at_beginning(linked_list *l, node *n) {
  n->next = l->head;
  l->head = n;
}

//insert new node at last
void insert_at_last(linked_list *l, node *n) {
  node *temp = l->head;

  while(temp->next != NULL) {
    temp = temp->next;
  }

  temp->next = n;
}

//function to insert a node after a node
void insert_node_after(node *n, node *a) {
  n->next = a->next;
  a->next = n;
}

//function to delete
void del(linked_list *l, node *n) {
  node *temp = l->head;
  if(temp == n) { //node to be deleted is head
    l->head = n->next;
    free(n);
  }
  else { //node to be deleted is not head
    while(temp != NULL) {
      if(temp->next == n) { //node previous to node to be deleted
        temp->next = n->next;
        free(n);
        break; //breaking the loop after deleting the node
      }
      temp = temp->next;
    }
  }
}

int main() {
  linked_list *l = new_linked_list(10);

  node *a, *b, *c; //new nodes to insert in linekd list
  a = new_node(20);
  b = new_node(50);
  c = new_node(60);

  //connecting to linked list
  /*
     ----     ----     ----     ----
    |head|-->| a  |-->|  b |-->|  c |-->NULL
    |____|   |____|   |____|   |____|
  */
  l->head->next = a;
  a->next = b;
  b->next = c;

  traversal(l);

  node *z;

  z = new_node(0);
  insert_at_beginning(l, z);
  z = new_node(-10);
  insert_at_beginning(l, z);

  z = new_node(100);
  insert_at_last(l, z);

  z = new_node(30);
  insert_node_after(z, a);
  z = new_node(40);
  insert_node_after(z, a->next);
  z = new_node(500);
  insert_node_after(z, a->next->next);

  traversal(l);

  del(l, l->head);
  del(l, z);
  traversal(l);

  return 0;
}
class Node():
  def __init__(self, data):
    self.data = data
    self.next = None

class LinkedList():
  def __init__(self, data):
    a = Node(data)
    self.head = a

def traversal(l):
  temp = l.head #temporary pointer to point to head

  a = ''
  while temp != None: #iterating over linked list
    a = a+str(temp.data)+'\t'
    temp = temp.next

  print(a)

def insert_at_beginning(l, n):
  n.next = l.head
  l.head = n

def insert_at_last(l, n):
  temp = l.head

  while temp.next != None:
    temp = temp.next

  temp.next = n

def insert_node_after(n, a):
  n.next = a.next
  a.next = n

def delete(l, n):
  temp = l.head
  if temp == n: #node to be deleted is head
    l.head = n.next
    del n
  else: #node to be deleted is not head
    while temp != None:
      if temp.next == n: #node previous to node to be deleted
        temp.next = n.next
        del n
        break #breaking the loop after deleting the node
      temp = temp.next

if __name__ == '__main__':
  l = LinkedList(10)

  a = Node(20)
  b = Node(50)
  c = Node(60)

  #connecting to linked list
  '''
     ----     ----     ----     ----
    |head|-->| a  |-->|  b |-->|  c |-->NULL
    |____|   |____|   |____|   |____|
  '''

  l.head.next = a
  a.next = b
  b.next = c

  traversal(l)

  z = Node(0)
  insert_at_beginning(l, z)
  z = Node(-10)
  insert_at_beginning(l, z)

  z = Node(100)
  insert_at_last(l, z)

  z = Node(30)
  insert_node_after(z, a)
  z = Node(40)
  insert_node_after(z, a.next)
  z = Node(500)
  insert_node_after(z, a.next.next)

  traversal(l)

  delete(l, l.head)
  delete(l, z)

  traversal(l)
class Node {
  public int data;
  public Node next;

  public Node(int data) {
    this.data = data;
    next = null;
  }
}

class LinkedList {
  public Node head;

  public LinkedList(int data) {
    Node a = new Node(data);
    head = a;
  }

  public void traversal() {
    Node temp = head; //temporary pointer to point to head

    while(temp != null) { //iterating over linked list
      System.out.print(temp.data+"\t");
      temp = temp.next;
    }

    System.out.println("");
  }

  //new node before head
  public void insertAtBeginning(Node n) {
    n.next = head;
    head = n;
  }

  //insert new node at last
  public void insertAtLast(Node n) {
    Node temp = head;

    while(temp.next != null) {
      temp = temp.next;
    }

    temp.next = n;
  }

  //function to insert a node after a node
  public void insertNodeAfter(Node n, Node a) {
    n.next = a.next;
    a.next = n;
  }

  //function to delete
  public void del(Node n) {
    Node temp = head;
    if(temp == n) { //node to be deleted is head
      head = n.next;
    }
    else { //node to be deleted is not head
      while(temp != null) {
        if(temp.next == n) { //node previous to node to be deleted
          temp.next = n.next;
          break; //breaking the loop after deleting the node
        }
        temp = temp.next;
      }
    }
  }
}

class ListMain {
  public static void main(String[] args) {
    LinkedList l = new LinkedList(10);

    Node a,b,c;
    a = new Node(20);
    b = new Node(50);
    c = new Node(60);

    //connecting to linked list
    /*
       ----     ----     ----     ----
      |head|-->| a  |-->|  b |-->|  c |-->NULL
      |____|   |____|   |____|   |____|
    */

    l.head.next = a;
    a.next = b;
    b.next = c;

    l.traversal();

    Node z;

    z = new Node(0);
    l.insertAtBeginning(z);
    z = new Node(-10);
    l.insertAtBeginning(z);

    z = new Node(100);
    l.insertAtLast(z);

    z = new Node(30);
    l.insertNodeAfter(z, a);
    z = new Node(40);
    l.insertNodeAfter(z, a.next);
    z = new Node(500);
    l.insertNodeAfter(z, a.next.next);

    l.traversal();

    l.del(l.head);
    l.del(z);

    l.traversal();
  }
}

Analysis of Linked List


A linked list is a linear data structure like an array but the size of the linked can be changed, unlike an array. However, to access an element from a linked list, we might traverse to the entire list, so accessing an element takes $O(n)$ time. Inserting is also $O(n)$ operation because we need to traverse the entire list when the node to be operated is at the last of the linked list.

We learned about a singly linked list i.e., we had a single link between two nodes. We can also have one more link between nodes to point to the previous node of any node which is called a doubly linked list. We are going to study about it in the next chapter.

node of doubly linked list

You can always check the articles in further reading to learn more about any topic. Also, make sure to download the BlogsDope app to stay tuned with us.

Somewhere, something incredible is waiting to be known
- Carl Sagan

Doubt? Ask question
Close

Welcome.please sign up.

Close

Welcome.please login.