Linked lists: what are they and how do they work?

9 min readJun 23, 2022

For computer scientists to be able to use data efficiently, they need to organize and store data in a particular way, which is why they use data structures, a collection of data elements grouped, such as arrays, linked lists, and stacks.

The purpose of data structure is to organize data for efficient storage, retrieval, and manipulation, so that data can be easily managed. The challenge is to select the right linear or non-linear data structure for the problem. There are several different types of data structures, and each is intended for certain kinds of applications. However, in this article, we will concentrate on linked lists. Specifically, we will learn what a linked list is, why we use it instead of arrays, and how to traverse, insert and delete nodes from a linked list.

What is a linked list?

There are several types of linked lists, including singly-linked lists, doubly-linked lists, circular linked lists, and circular doubly-linked lists. However, all of them are linear data structures, consisting of an ordered collection of data and a series of nodes (each called a node) interconnected. Imagine it as a train! Everything is connected to everything else.

Each linked list node has two parts, the data, and the next node reference:

Array vs. linked list

- Array

Due to the fact that arrays are made from static memory, their size is fixed and can neither be extended nor decreased. For example:

Int [] a = new int [5];a[5]=0;

An ArrayIndexOutOfBoundsException is thrown because the index exceeded the array’s length.

Arrays have contagious memory, Every cell follows the one before it in the array, allowing direct access to the array. You can ask for a specific element of an array by saying:

Int [] array = {1, 2, 3, 4};System.out.println(array [2]);

By looking at index 2, we can see where element 3 is located, so element 3 will be printed.

- Linked list

Since linked lists contain dynamic memory, you can increase or decrease their size as needed. They, however, do not contain contagious memory locations. In memory, nodes do not necessarily follow one another. Therefore, they are not accessible directly like arrays are. Each node must be searched in order to find the element we are searching for.

But what’s wrong with using an array?

Shifting is the problem in arrays. Adding a new element at first requires slow shifting. Linked lists, on the other hand, make operations such as insertion and deletion easier to implement without requiring shifting, and will have a better time complexity.

Singly Linked Lists

A single linked list is composed of nodes with a data part and an address or link part that points to the next node in the sequence. There is a reference variable that points to the first node of the list and that has no purpose other than to point to the first node. The common name for this variable is Head and it points only to the first node. The last node, however, points to Null.

***A linked list containing three elements***

Java requires two classes to implement a linked list: the node class and the linked list class. We will need to use the node class to create node objects, which have a data field and a link field. Below is a representation of a node class:

class node

Next, let’s look at the linked list class. This class defines a head reference variable. Furthermore, it defines methods for manipulating the list, such as insertion, deletion, searching, and printing. Below is an example of a linked list class:

linked list class

Before we explore the operations of a linked list, here are some things to keep in mind:

A representation of an empty linked list

Field of nodes in the linked list

As mentioned previously, we could have more than 20 fields per node Here is a node with more than one field:

Moving to the next node

What is the process for moving to the next node? It may seem obvious to some that if the head points to the first node, then we will traverse to the next node with:

head=head.next;

Since each node points to the next node and not to the previous ones, this is inefficient, causing errors and we will lose access to the first node. Therefore, we will create a temporary variable called HelpPtr, which is a help pointer that allows us to traverse from one node to the next without losing the entire list. When we start, our HelpPtr will point to the first node. Here’s what our declaration will look like:

Node HelpPtr = head;

In the lines of code above, HelpPtr points to whatever memory location Head points to, so they are both pointing to the same memory location (make HelpPtr point to the first node).

In our previous representation, we could say the first node could be printed by these lines of code

System.out.println(HelpPtr.data);System.out.println(head.data);

The next line of code will print the next node if it exists, and so on

System.out.println(HelpPtr.next.data);

Some operations on singly-linked lists

- traversing in a singly linked list

Traversing is almost always the most common operation within a linked list. In order to traverse a list, each node must be visited once to perform some operation. Here are some steps involved in traversing all nodes and printing them:

1- Creating our helpPtr is the first step. To traverse the list, we save the value of head into helpPtr, which is a reference to the first node.

2- Secondly, we create a while statement that states that we will traverse the list as long as helpPtr does not equal null. Otherwise, if it is null, we have reached the end.

3- Whenever helpPtr does not equal null, the data that helpPtr refers to will be printed.

4- Following that, we move helpPtr over to the next node.

5- Eventually, helpPtr will equal null, and we will exit the loop.

A second method of traversing a linked list is to search for a specific data item. Below is an example:

We are doing the same thing as traversing the list and printing it, only with an if statement to make sure we only print the data we are looking for

- Insertion in a singly linked list

The next operation will be to insert nodes into the list and to do that, we need to understand how to traverse the list as we did earlier. first, we need to know that we can insert an element from a list from:

beginning
middle
end

Adding a node to the beginning and middle of the linked list

There are four steps involved in adding nodes to a linked list:

1- create a new node object.

2- We need to know the predecessor of the new node to locate its insertion point in the list.

3- the new node should be pointed to its successor (the node that comes after it).

4- Next we must point the predecessor node to the new node.

So the list won’t be lost, point the new node to the successor and the predecessor to the new node. The following diagram shows the steps:

It is simple, you just need to point or connect the new node to the list and let the list point or connect to the new node using the predecessor and successor scenarios. In our previous diagram, we learned how to add a new node to the middle of the linked list; now we’ll learn how to add a new node to the front. There are two possible scenarios for adding a new node to the front of a linked list:

1- The list might be empty, so the head point to null

2- The linked list contains nodes that already exist

Let’s look at both scenarios:

1- Add a new node to an empty list:

As the new node will be the first of the list, we will make it point to null, and we will make the Head point to the new node. Therefore, it will be the first and the last node of the list.

If the list is empty, add the address of the new node to the head, making it point to the new node.

2- Adding a node to a list that already contains nodes

In the case of a non-empty list, the head will store a reference to the current first node, and that reference must be saved into the new node to reference the previous node. and We must store the address of the new node in the head to make the head point to the new node.

- Adding a node at the end of the linked list

To add to the end of the linked list, we need to traverse the entire list using HelpPtr.

While (HelpPtr.next !=null){HelpPtr = HelpPtr.next ;}

You can see that the condition, in this case, is:

HelpPtr.next!=null

In this case, we have used next because HelpPtr must point to the predecessor. The reason for the change is that we need to add a new node at the end of the list. Therefore, after traversing, HelpPtr must point to the last node, which will be the predecessor node. It will then point to the new node that follows it. We must therefore set HelpPtr.next!=null as the condition of our while loop The following diagram shows the steps:

Here is the Insertion code (front, middle, end):

- Deletion in a singly linked list:

The following are four deletion scenarios that need to be considered:

1- Deleting the first node

2- Deleting any middle node

3- Deleting the last nod

4- Deleting the only node in the last

1- Deleting the first node

The Head must point to the second node for the first node to be deleted. Therefore, we save the reference of the second node in the head which is saved in the next of the first node. Once this is done, the Java garbage collector deletes the first node.

2- deleting any middle node

When we want to delete a node in the middle of the list, the predecessor of the node that we want to delete must point to the successor of the node that we want to delete.

We need the predecessor to point to the successor, which means the node with data 2 needs to point to the node with data 6. To do this, we need to take the address of the node with data 6 that is stored in the next of the node that we want to delete, and then save it to the next of the predecessor, which is a node with data 2. As a result, the node with data 4 will be deleted by the Java garbage collector.

3- Deleting the last node

We simply need to make the next of the predecessor, which is the node with data 4, point to null. This is because the data is stored at the next node with data 6. And finally, the last node is deleted by the Java garbage collector.

Code of deletion (front, middle, end):

In conclusion, I hope you have gained a better understanding of linked lists, including how to insert, delete, and traverse them. Enjoy writing your own linked list program!

Please feel free to add any information you have about linked lists in the comments section!