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.

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).


  • 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.

Linked List

Structure of Linked list

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

  1. Data part – It is for storing element data.
  2. Link partThis 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

Declaring, Initializing and Implementation in C language:

Declaration –

Linked lIst node

A Node of Linked List

  • 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;
typedef node *list;

Initialization and implementing Linked list in C –

// C program to traverse a link list
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()
    //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));
    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;
    return 0;

10 20 30

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>();
        //Traversing and printing data of linked list.
 * 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 = 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) { = next;

10 20 30

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

Few points:

  • 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

Knowledge is most useful when liberated and shared. Share this to motivate us to keep writing such online tutorials for free and do comment if anything is missing or wrong or you need any kind of help.

Keep Learning… Happy Learning.. :)