Introduction to Linked List – Explanation and Implementation

Linked list is a linear data structure, linear refers to storing the elements sequentially in the form of nodes.

Unlike arrays, here each element is linked using pointers rather storing them continuously.

1. Advantages of using Linked list against Array:

• Size of the block should be known in advance in Array but not in Linked List.
• Insertion and Deletion are costly in array even if related info is known. Say deletion of a known element or insertion to preceding/succeeding element, here in both case linked list takes O(1) time however array causes O(n).

2. Disadvantage:

• Consumes more memory.
• Random access is not possible.
• Performance wise array is better due to poor locality of reference in Linked List especially spatial locality.

Say we want to store elements 10, 20 and 30 in the linked list data structure.

In the image above 3 nodes are used, each having 2 parts-

1. Data part – It is for storing element data.
2. Link part – This part has a reference  which holds the address of the next node.

Each node is pointing to next node and next is to next. The last one contains Null in its reference section. Head is used to point the starting node using which linked list is accessed.

Thus, Linked list can be visualized as a chain of nodes where every node point to the next node

3. Declaring, Initializing and Implementation in C language

3.1. Declaration

• For Data, int data;
• For Link/Next, it is going to point a structure of the same type. struct node_type *link;

Thus the declaration would be,

typedef struct node_type{
	int data;
	struct node_type *link;
}node;
					
typedef node *list;

3.2. Initialization and implementing Linked list in C

// C program to traverse a link list
#include<stdio.h>
#include<stdlib.h>
 
//DECLARATION
struct node 
{
    int data;
    struct node *next;
};
 
// This function prints contents of linked list from given node
void printLinkedList(struct node *list)
{
    while (list)
    {
        printf(" %d ", list->data);
        list = list->next; // accessing and assigning the next element of list
    }
}
 
// Main method to initialize the program
int main()
{
    //INITIALIZATION
    //Declare and allocate 3 nodes in the heap 
    struct node* head;
    struct node* first = (struct node*)malloc(sizeof(struct node)); 
    struct node* second = (struct node*)malloc(sizeof(struct node));
    struct node* third = (struct node*)malloc(sizeof(struct node));
     
    //ASSIGNINMENT
    first->data = 10; //assign data in first node
    first->next = second; // Link first node with second 
     
    second->data = 20; //assign data to second node
    second->next = third; 
     
    third->data = 30; //assign data to third node
    third->next = NULL;
 
    head = first;
    printLinkedList(head);
     
    return 0;
}

Output:-

10 20 30

4. Declaring, Initializing and Implementing Linked List in Java

package com.codingeek.datastructure.linkedlist;
 
public class SinglyLinkedListTraversal {
 
    //Main to initiate the program.
    public static void main(String[] args) {
         
        //Initializing linked list.
        LinkedList<Integer> linkedList = new LinkedList<Integer>();
        linkedList.add(10);
        linkedList.add(20);
        linkedList.add(30);
         
        //Traversing and printing data of linked list.
        linkedList.traverseAndPrint();
    }
 
}
 
/*
 * This class holds the references and performs all operation on link list.
 */
class LinkedList<T> {
    private Node<T> head;
    private Node<T> tail;
 
    // Adds a single node at the end of link list.
    public void add(T element) {
        Node<T> node = new Node<T>(element);
        if (head == null) {
            head = node;
            tail = node;
        } else {
            tail.setNext(node);
            tail = node;
        }
    }
 
    // Traverses current state of linked list and print data members.
    public void traverseAndPrint() {
        Node<T> current = head;
        while (current != null) {
            System.out.print(" " + current.getData());
            current = current.getNext();
        }
    }
}
 
/*
 * Object of this class is a single node in linked list.
 */
class Node<T> {
    T data;
    Node<T> next;
 
    public Node(T element) {
        data = element;
        next = null;
    }
 
    public T getData() {
        return data;
    }
 
    public Node<T> getNext() {
        return next;
    }
 
    public void setNext(Node<T> next) {
        this.next = next;
    }
 
}

Output:-

10 20 30

Note:- Above is the basic representation of linked list data structure in Java but Java also provides its implementation – java.util.LinkedList. We will always use this in real-world programming solutions.

5. Few points about Linked Lists

• A Linked list can be of type Singly Linked list, Doubly linked list or Circular Linked list.
• It can be implemented as queue or stack.
• Applications of Linked list
  1. Memory management in OS, Symbol table management
  2. MRU/LRU(Most/Least recently used)
  3. Tree, Graph
  4. Stack and Queue
  5. Hashing etc. and many

Helpful Links

Data Structure tutorials
Algorithm Tutorials

All examples are hosted on Github.

An investment in knowledge always pays the best interest. I hope you like the tutorial. Do come back for more because learning paves way for a better understanding

Do not forget to share and Subscribe.

Happy coding!! ?

Recommended -