Linked List in Java

Linked List in Java

Understanding Linked List in Java

Linked list is a linear data structure that we can use in Java Programming Language for storing large amount of data with ease. The data stored in Linked List is not in a contiguous manner, but each data is stored at a different location, which can be accessed according to one’s need. Linked List is a preferred data structure over arrays, as inserting and deleting data in linked list is easier than in array.

How to make a Linked List in Java

A linked list is a linear data structure that is made up several nodes, which is further divided into two parts-:

  1. Node -: This part stores the data.
  2. Link -: This part stores the address of the memory location, where the next data of the list is stored.
struct Node 
{
  int Data; //for storing a specific data
  Struct Node* ptr; //for storing the address of the next node
};

Linked List as a part of Collection

There are various different frameworks in Java which we can use for storing and operating efficiently on our data. Such is a framework known as Collection framework in Java. In this framework there are various different classes and interfaces are present using which we can code Linked List in Java in a very easy manner as it has a pre-defined class LinkedList stored in it, which has functions like

  • add()
  • delete()
  • search()
  • reverse(), etc

which we can use for operating on a linked list.

Linked list in java

Some of the pre-defined function of LinkedList class

Method nameMethod Description
void addFirst(E e)This method inserts an element at the beginning of the list
void addLast(E e)This method inserts an element at the end of the list
void add(int index, E element)This method inserts an element at the specific position of the list
void clear()It is used to clear all the elements from the list
boolean contains(Object o)This method returns true if the specific element is present in the list, otherwise return false
element()This element let us view the first element of the list
getLast ()This method gives us the last element of the list
lastIndexOf(Object o)This method returns the index of the last occurrence of a specified element
size()This method returns the size of the list
toArray()This method converts the list into an array

Types of Linked Lists

Although linked list is a linear data structure, there are a few variations of Linked List which we can use according to our needs. Every variation has some benefits than the other variation. Lets see all the variations of a Linked List

  1. Singly Linked List -: It is the most basic linked list, which is made up of several nodes, which can further  be divided into two parts i.e; data and link. One major drawback of this linked list is that it can only traverse in a single direction(from head to tail).
  2. Doubly Linked List -: This is a successor of a normal linked list. Nodes of a double linked list has three parts, one for storing data and the other two for storing the addresses of the previous nodes as well as the next node, which enables a doubly linked list to traverse in both the direction, thus overcoming the drawback of a singly linked list.
  3. Circular Linked List -: Circular Linked List is a combination of both singly and doubly linked list. Nodes of a circular linked list is similar to  that of a singly linked list, but the main difference in a singly and circular linked list is that, the last node of the circular linked list does not point to null, but it points to the first node of the linked list, which allows it to traverse back in the linked list, thus overcoming the drawback of memory usage of doubly linked list.

 

 

Types of Linked List in Java

Linked List vs Array

Linked List

  • Operation like insertion and deletion are easier.
  • Data is stored in a continuous manner
  • No need for pre-allocating the size of the list
  • Memory loss is comparatively low

Array

  • Operation like searching and traversing are easier.
  • Data is stored in a contiguous manner.
  • User need to define the size before inserting the data.
  • Memory loss is comparatively high