Cover Photo by Danielle MacInnes on Unsplash

Linked Lists are one of the simplest yet most commonly used data structures. Linked Lists are used to implement more data structures such as stacks, queues, graphs, etc. We will be going through the basics of Linked Lists.

Let’s get technical now.

What is a Linked List?

Linked List is nothing but a collection of elements called Nodes. It’s that simple!!

A node is a very simple object with just two properties. It is a variable to store data and another variable to store the memory address of the next node in the list. If you look at the below image, each node contains a data known as a key and a pointer which points to the address of the successive node known as next. Head is a special name given to the first node of a list, while Tail is a special name given to the last node of a linked list.

A node only knows about what data it contains and who its neighbour is.

Source: Educative.io

What’s so special about a linked list is that it is a linear data structure where the position of the node does not determine the location where it is stored in the memory. As I explained above, the memory location of the successive node is stored in the current node. This means that Linked Lists are dynamic — you can add or remove nodes from your linked list while your program is running.

Linear Data Structures

A linear data structure traverses the data elements sequentially, in which only one data element can directly be reached. In other words, you can travel along with a linear data structure in one direction by accessing each element one by one — nodes in linked lists.

Let’s summarize what we have learned up to now.

Summary

• Nodes are the elements of a linked list.

• Each node has a data (key) and a pointer to its successor node, which is known as next.

• The head property refers to the first member of the linked list.

• The last element of the linked list is known as the tail.

Types of Linked Lists

There are several types of linked lists.

• Singly linked list — Elements may only be traversed in the forward direction.

• Doubly linked list — Elements can be traversed in both forward and backward directions. Nodes have an extra pointer known as prev, which points to the preceding node.

• Circular linked lists — Linked lists in which the head's previous(prev) pointer points to the tail and the tail's next pointer points to the head.

Basic Operations

Following are the basic operations supported by a list.

• Insertion − Adds an element at the beginning of the list.

• Deletion − Deletes an element at the beginning of the list.

• Display − Displays the complete list.

• Search − Searches an element using the given key.

• Delete − Deletes an element using the given key.

Advantages of using Linked Lists

Dynamic data structure

A linked list is a dynamic data structure, so it can grow and shrink at runtime by allocating and deallocating memory. So there is no need to give the initial size of the linked list, unlike arrays.

Insertion and Deletion

Insertion and deletion of nodes are really easier. Unlike arrays, here, we don’t have to shift elements after insertion or deletion of an element. In a linked list, we just have to update the address present in the next pointer of a node.

No Memory Wastage

As the size of a linked list can increase or decrease at run time, so there is no memory wastage. In the case of an array, there is a lot of memory wastage. For example, if we declare an array of size ten and store only six elements in it, then space of 4 elements are wasted. There is no such problem in linked lists as memory is allocated only when required.

Implementation

Data structures such as stacks and queues can be easily implemented using linked lists.

Disadvantages of Linked Lists

Memory Usage

More memory is required to store elements in a linked list as compared to an array. Because in a linked list, each node contains a pointer, and it requires extra memory for itself.

Traversal

In a linked list, traversing elements or nodes is challenging. We cannot access any element at random, as we can in an array by index. For example, if we wish to reach a node at position n, we must first traverse all nodes before it. Therefore, a lot of time is required to access a node.

Reverse Traversing

Reverse traversal is extremely challenging in a linked list. It is simpler in the case of a doubly-linked list, but more memory is required for the back pointer, resulting in memory wastage.

---

We will look at how to implement a Linked List in Java and discuss how the basic operations of a Linked List work in the next article.

Thank you for reading ❤

If you feel that something should be added to the above article, feel free to leave a comment below.

Happy Coding!!