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

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.

parts of node

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;
Int [] array = {1, 2, 3, 4};System.out.println(array [2]);

- 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
class node
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
head point to null
fields of node
head=head.next;
Node HelpPtr = head;
linked list with one node
System.out.println(HelpPtr.data);System.out.println(head.data);
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:

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

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

insertion in the middle of the list

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.

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 ;}
HelpPtr.next!=null

- Deletion in a singly linked list:

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

deleting middle node
linked list
deleting the last node

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Aseel Bahakeem

Aseel Bahakeem

This is where I come to learn and to spread awareness