Singly Linked List Implementation in Java

Introduction : Linked list is a linear and non-indexed data structure. Arrays and List in java , stores the data in contiguous memory locations but linked list stores the data at random locations and link node to another node.

Advantage : Linked list optimize the memory allocation as compare to Arrays and List.If programmer creates an Array with fixed size, even Array is not fully filled , but it will hold the memory location.In case of linked list, wastage of memory locations are very minimal.If we talk about the performance in terms of insertion and deletion, Linked list is more faster than Array and List in java.Like List, size of Linked list is dynamic.

Drawback : Random access is not allowed in Linked list. To access elements, need to traverse through the nodes starting from root node till the element position.Extra memory is required to store the address of next node.

Representation : A linked list is represented by a pointer to the first node (root node)of the linked list.If linked list is empty , then root node will be NULL.Each node in a linked list consists of two parts:

  1. Data
  2. Pointer to the next node

In Java, LinkedList can be represented as a class and a Node as a separate class. The LinkedList class contains a reference of Node class type.

Types : Majorly, there are three types of linked list.

  1. Singly Linked List
  2. Doubly Linked List
  3. Circular Linked List

We will talk about the properties of all three types of linked list and their implementation in JAVA.In this post, we will write the implementation of Singly Linked List.

Implementation of Singly Linked List : Singly linked list consists of only one pointer to the next node.Each node will have data and only one pointer .We can traverse the singly linked link in forward direction only. Pointer of last node will be always NULL.

We will start with the simpler implementation where we can add the element in linked list and display the data. We are not going to use the Generics now, but later we will have implementation with Generics type.

Node: Node class consists of data and node (pointer to next node). We can override the hashCode(), equals() and toString methods.

 

SinglyLinkedList : This class will have root node and size as instance variables. We have method add(Object data) , which will add the element at end of the linked list.

public void add(Object data) :

Steps:

  1. If data is null, then don’t do anything. This implementation ensure that, it will not allow null entry.
  2. If node is null, it means size of singly linked list is 0. In this case, create new node and assign it to root node.
  3. If node is not null, we should get the last node of the singly linked list and set the pointer node of last node as newly created node. This add implementation will have time complexity of O(n) , because to get the last node, we need to traverse through the entire nodes starting from root node. We will optimize the time complexity to add any element in constant time O(1).
  4. Added supported methods to get last node, next node, size of linked list and toString() method.[ Try Yourself ]

Create object of SinglyLinkedList and add some object in main method. After running the main method  we could see the below results on console.

Let’s see how does it look (after adding three elements) in debug mode in eclipse.

Now, we will try to optimize the add operation .Our goal is to add the element in constant time irrespective of size of the linked linked. In above implementation, we need to traverse through all the nodes to find out the last node, hence time complexity became O(n) . To get rid of traversing the nodes every time, we can add one instance variable “lastNode” to SinglyLinkedList class and set the value on every add method call. Refer the below implementation.

In next post, we will create Singly Linked List using Generics.

Hope you like this post. Please give your valuable suggestions/comments.

You may like –

 

 

Top