A Linked List is a linear data structure used for storing a collection of elements. Unlike arrays, linked lists use nodes to store elements which are not stored in contiguous memory locations.

In this article, you will learn what linked lists are, how they work, and how to build one.

While the concepts discussed are not specific to any particular programming language, this article will use Java to demonstrate how to create a linked list programmatically.

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

Here, you can see that the addresses of the nodes are not necessarily immediately sequential. The first node has an address of 200 and the second node has an address of 801, instead of 201 as you might expect.

Then how are the nodes stored linearly?

Even though the nodes are not in a contiguous memory, the nodes are stored linearly through links. Every node has the address of its succeeding node. That is how each node can access its succeeding node.

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

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

The first node of the linked list is called the `head` node. It is the starting point of a linked list.

The last node is called the `tail` node. As there is no node after the last node, the last node always points to the `null`.

A `null` pointer does not point to any memory location.

## How to Create a Linked List Programmatically

At this point, you should have basic knowledge of how a linked list works and its structure. Let’s create a linked list with the following steps:

• Create node.
• Connect nodes.
• Append nodes.
• Insert nodes.
• Delete nodes.

## 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:

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 {

}

}``````

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) {
}``````

### 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) {
}
``````

### 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 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) {
}``````

### 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;
}``````

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;
}
}

}

Node node1 = new Node(11);

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

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

public void append(Node newNode) {

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

}

public void insert(Node newNode, int index) {

if (index == 0) {
newNode.next = current;
} 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 previous = null;
int deletedValue = -1;

if (index == 0) {
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;
}
}

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

}
}

}

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

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

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