Coding Basics: Understanding How Linked Lists Work – A Beginner’s Guide

A Linked List serves as a linear data structure employed to contain a group of elements. In contrast to arrays, linked lists utilize nodes to hold elements, and these elements are not stored in adjacent memory locations.

This article covers the fundamentals of linked lists, explaining their definition, functionality, and construction process.

Although the concepts discussed are language-agnostic, Java will be used in this article to illustrate the implementation of a linked list.

What is a Linked List?

A linked list is a collection of nodes where each node contains data as well as the memory address of the next node in the list.

Illustration of a linked list with three nodes

In this context, the addresses of the nodes are not strictly sequential. For instance, the first node might have an address of 200, while the second node could be at address 801 instead of the expected sequential address like 201.

However, despite not being stored in contiguous memory, the nodes are arranged linearly through links. Each node contains a reference to its successor, enabling access to the next node in the sequence.

Nodes in a Linked List

Nodes are the building block of the linked list. After all, a linked list is a collection of nodes.

A node in a linked list consists of two parts:

• data which denotes the value of the node.
• next which is a reference to the succeeding node.

Head and Tail in a Linked List

As mentioned earlier, a linked list is a collection of nodes.

Illustration of a linked list showing the head and tail

The initial node of a linked list is termed the head node, marking the beginning of the linked list.

Conversely, the final node is known as the tail node. Since there are no nodes following the tail node, it always references null.

A null pointer indicates the absence of a memory location to point to.

How to Create a Linked List Programmatically

By now, you should possess a foundational understanding of linked lists and their structural mechanics. Now, let’s proceed to construct a linked list through the following steps:

1. Node Creation
2. Node Connection
3. Node Appending
4. Node Insertion
5. Node Deletion

How to Create a Node in a Linked List

As you know, a node consists of two parts: the data and the address to the next node.

Here’s how you can create a class called Node:

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

The Node class represents a node in a linked list, with two instance variables: data (holds the data stored in the node), and next (holds a reference to the next node in the list).

The constructor takes an int argument data to initialize the data variable and sets the next variable to null by default.

Now, you can simply create nodes and add data to them by creating new instances of the Node class:

// create nodes
Node node1 = new Node(11);
Node node2 = new Node(18);
Node node3 = new Node(24);

In the code above, we created three nodes:

How to Link the Nodes in a Linked List

After creating the nodes, you must connect them to form a linked list.

To do this you first need to create a linked list with a head node.

class LinkedList {

    Node head;

        LinkedList() {
        this.head = null;
    }

}

Initially the head node is set to null because there are no nodes in the linked list yet.

Now to connect the nodes together in a Linked List, you can start by setting the head node to the first node in the list, in this case node1.

head = node1;

Then make the next of node1 point to node2, and the next of node2 point to node3. That is:

node1.next = node2;
node2.next = node3;

You have successfully created a linked list and connected the nodes.

How to Append a Node to Linked List

Appending a node means adding a node to the end of a linked list. There are two cases to consider when appending a node:

• Appending to an empty linked list.
• Appending to a non-empty linked list.

How to Append a Node to an Empty Linked List

If there are no nodes in a linked list, it is an empty linked list. To append a node to an empty linked list, you must first make sure the linked list is empty. You can do this by checking if the head node is null.

If the head node is null then you can simply set head to the new node:

if (head == null) {
    head = newNode;
}

How to Append a Node to Non-Empty Linked List

If there are one or more nodes in a linked list, it is a non-empty linked list.

To append a node to a non-empty linked list, make the last node link to the new node.

Unlike arrays, we cannot access any elements in a linked list directly. We must traverse from the head node to the last node.

To do that, create a temporary pointer (you can call the pointer current) that points to the head node.

Next, make current point to its next node, till the next of the current node points to null.

When the next node of current is null, you can then make the next of the current node point to the new node. That is:

while (current.next != null) {
    current = current.next;
}
current.next = newNode;

How to Insert a Node in a Linked List

Inserting a node means adding a node to a given index. There are two cases to consider when inserting a node:

• Inserting a node at the first index.
• Inserting a node at a given index.

How to Insert a node at the First Index

To insert a node at the first index:

• make next of the new node point to the head node
• set the head to the new node

if (index == 0) {
    newNode.next = head;
    head = newNode;
}

How to Insert a Node at Any Position

Let’s suppose you want to add a node at index 2 in the linked list above.

To insert a node at index 2, you must traverse the node that comes before index 2.

Next, create a new node and make the next of the new node point to the next of the current node.

Make the next of current point to the new node.

Here’s the code to do all this:

for (int i = 0; i < index - 1 && current != null; i++) {
    current = current.next;
}
if (current != null) {
    newNode.next = current.next;
    current.next = newNode;
}

How to Delete a Node in a Linked List

There are two ways to delete nodes in a linked list:

• Deleting the head node.
• Deleting a node at a given position.

How to Delete the Head Node

Deleting the head node of a linked list is simple. You can store the data of the head node in a temporary variable if it needs to be accessed later. Then set the head pointer to point to the next node after the head node.

if (index == 0) {
    deletedValue = head.data;
    head = head.next;
}

How to Delete a Node at a Given Position

Suppose you want to delete the node at index 2 in the diagram below:

You can delete the node at index 2 by making the node at index 1 point to the node at index 3.

To delete a node you must access the node you want to delete and the node before it. Take two temporary pointers (you can call the pointers previous and current). Let previous point to null and current point to the head node.

Now, move current one step forward and move previous to current till you reach index 2.

Make the next of previous point to the next of the current node.

Then store the data of current in a variable for future use.

After removing the link to the node at index 2, it is no longer accessible through any reference in the linked list.

It’s important to note that when removing a node from a linked list, you don’t need to explicitly delete the node itself at the given index. This is because the removed node will be automatically handled by the garbage collector when it is no longer reachable through any references.

However, in languages like C or C++, which do not have automatic garbage collection, you need to manually delete the node when it is no longer needed to avoid memory leaks and wasted memory resources.

for (int i = 0; i < index && current != null; i++) {
    previous = current;
    current = current.next;
}

if (current != null) {
    deletedValue = current.data;
    previous.next = current.next;
}

Complete Linked List Code

The code below shows a complete linked list. You can create, append, insert, delete, and display the nodes in the linked list:

class Node {

	int data;
	Node next;

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

class LinkedList {

	Node head;

	LinkedList() {
		this.head = null;
	}

	public void createLinkedList() {

		Node node1 = new Node(11);
		this.head = node1;

		Node node2 = new Node(18);
		node1.next = node2;

		Node node3 = new Node(24);
		node2.next = node3;
	}

	public void append(Node newNode) {

		Node current = this.head;

		if (current == null) {
			this.head = newNode;
		} else {
			while (current.next != null) {
				current = current.next;
			}
			current.next = newNode;
		}

	}

	public void insert(Node newNode, int index) {

		Node current = this.head;
		if (index == 0) {
			newNode.next = current;
			this.head = newNode;
		} else {

			for (int i = 0; i < index - 1 && current != null; i++) {
				current = current.next;
			}
			if (current != null) {
				newNode.next = current.next;
				current.next = newNode;
			}

		}

	}

	public int delete(int index) {

		Node current = this.head;
		Node previous = null;
		int deletedValue = -1;

		if (index == 0) {
			deletedValue = this.head.data;
			this.head = this.head.next;
			return deletedValue;
		}

		else {
			for (int i = 0; i < index && current != null; i++) {
				previous = current;
				current = current.next;

			}
			if (current != null) {

				deletedValue = current.data;
				previous.next = current.next;
			}
			return deletedValue;
		}
	}
	
	public void displayLinkedList() {

		Node current = this.head;
		while (current != null) {
			System.out.println(current.data);
			current = current.next;

		}
	}

}

class Main {
	public static void main(String[] args) {
		LinkedList l1 = new LinkedList();
		Node newNode1 = new Node(22);
		Node newNode2 = new Node(43);
		Node newNode3 = new Node(5);
		l1.createLinkedList();

		l1.append(newNode1);
		l1.insert(newNode2, 0);
		l1.insert(newNode3, 2);
		l1.delete(2);
		l1.displayLinkedList();
	}
}

Wrapping Up

The linked list data structure can be used in various applications, such as web browsers and music players.  

For example, in a web browser, the browser history can be stored as a linked list. Each page visited can be represented by a node, with the link pointing to the next page visited. This allows for easy navigation through the history, by simply traversing the linked list.

Similarly, in a music player, the playlist can be represented as a linked list. Each song can be represented by a node, with the link pointing to the next song in the playlist. This allows for easy navigation through the playlist, by simply traversing the linked list.

It is not very likely that you will create a linked list for your applications, as almost every programming language has a built-in linked list.

However, creating one and understanding its implementation can deepen your knowledge of the data structure. This knowledge can help you determine when to use a linked list over other data structures in real-life applications.