LINKED LIST IN JAVA

A linked list is a linear data structure, in which the elements are not stored at contiguous memory locations.

Every element in the linked list is a separate object with a data part and address part. Each of these elements is known as a NODE. Each node contains a data field and a reference(link) to the next node in the list.

It is a part of the Collection framework present in java. util package.

ArrayList VS Linked List

Both ArrayList and linked lists have the same methods as both are implemented using the list interface and they contain objects of the same type.

However, they are built are not built in the same manner and have several differences.

ArrayList:

• ArrayList internally uses a dynamic array to store the elements.
• ArrayList is better for storing and accessing data.
• An ArrayList class can act only as a list because it implements only the List interface.
• Manipulation with ArrayList is slow because it internally uses an array and if we want any element to be removed from the array, all the bits are shifted in memory.
• It is best to use when we have to randomly access items or while deleting or adding elements at the end of the list.

Linked List:

• LinkedList internally uses a doubly linked list to store the elements.
• Linked List is better for manipulating data.
• LinkedList class can act as a list and queue both as it implements both List and Deque interfaces.
• Manipulation with LinkedList is faster than ArrayList because it uses a doubly linked list and hence no bit shifting is required in memory.
• It is best to use when we need to add and remove items from the beginning or middle of the list and random access is not required.

Advantages and Disadvantages of a Linked List

Advantages :

• It can grow and shrink at runtime by allocating and deallocating memory.
• Insertion and deletion of nodes are really easier as no shifting of elements required.
• As the size of the linked list can increase or decrease at run time so there is no memory wastage.

Disadvantages :

• More memory is required to store elements in the linked list as each node contains a pointer and it requires extra memory for itself.
• Elements or nodes traversal is difficult in a linked list and random access of elements not possible.
• In the linked list reverse traversing is really difficult. In the case of a doubly-linked list, it's easier but extra memory is required for the back pointer hence wastage of memory.

Basic Structure

The linked list contains a sequence of nodes. As discussed earlier the linked list consists of two parts: the data part and the reference part (which points to the next node). In the case of a doubly-linked list, there will be an extra previous part also.

The first node is called the head. The last node is called tail which points to null. If the linked list is empty, then the value of the head is NULL.

Implementation of a node

Generic Type-

public class ListNode<T>{
       T data;
       ListNode<T> next;
}

Now let’s see some basic implementations!!!

Singly Linked List in Java

A linked list of integer type:

Length of a Linked List

Insert a new node

a) At the head of the linked list:

b) At the tail of the linked list:

c) At a specified position of the linked list

Delete a node

a) From the head of the linked list:

b) From the tail of the linked list:

c) From a specified position of the linked list

Reverse the Linked List

Print elements of the Linked List

Let’s try this now!!!

Output:

Inserting from begining
4 3 2 1
Inserting from end
4 3 2 1 5 6
Insert at position 3
4 3 7 2 1 5 6
Delete from begining
3 7 2 1 5 6
Delete from end
3 7 2 1 5
Delete from position 2
3 2 1 5
Reverse of the Linked List
5 1 2 3
Length of the Linked List:4

Complete Code:

For more practice problems checkout HackerRank.

LinkedList Methods

Some basic methods:

• addFirst()-Adds an item to the beginning of the list
• addLast()-Add an item to the end of the list
• removeFirst()-Remove an item from the beginning of the list
• removeLast()-Remove an item from the end of the list
• getFirst()-Get the item at the beginning of the list
• getLast()-Get the item at the end of the list
• get(index)-access an element from the LinkedList
• set(index, value)-change elements of the LinkedList

Output:

Adding elements
[Rita, Gita, Hari, Priya, Siya, Shyam]
Deleting elements
[Gita, Hari, Priya, Siya]
Element at First:Gita
Element at Last:Siya
Element at 2nd index:Priya
[Gita, Hari, Sapna, Siya]

That’s it from my side. I hope you enjoyed reading this article 😊.

If you want to get connected with me, please follow these links

LinkedIn-https://www.linkedin.com/in/sapna2001/

Github-https://github.com/Sapna2001

Website-https://sapna2001.github.io/Portfolio/

Quora-https://www.quora.com/profile/Sapna-191

And if you have any suggestions, feel free to get in touch with me over LinkedIn & the comment section is also all yours.

If you liked this story, hit the clap button as it motivates me to write more & better.

Thanks for reading!!!!