Linked List Implementation in Java

We know that LinkedList class in Java is a doubly-linked list implementation of the List interface. This post provides an overview common techniques to manually implement a linked list in Java programming language.


 

We know that each node of a linked list contains a single data field and a reference to the next node in the list. The nodes of the linked list are allocated in the heap memory during runtime by the JVM. We can use constructor of the Node class to initialize data field and next pointer.

 

 
There are several methods to construct a singly linked list in Java –
 

1. Naive method

Simple solution would be to allocate memory for all individual nodes of the linked list, set their data and then rearrange their references to build the complete list.

linked list implementation

Download   Run Complete Code

 

2. Single line

We can write above code in a single line by passing next node as an argument to the new Node() function –

linked list implementation single line

 

Download   Run Complete Code

 

3. Generic method

Both of the above methods are not pratical when number of nodes increases in the linked list. If the keys are given in any container, such as an array, vector or set, we can easily construct a linked list by traversing the container as shown below:
 

Download   Run Complete Code

 

4. Standard Solution

Standard solution adds a single node to the head end of any list. This function is called push() since we’re adding the link to the head end which makes the list look a bit like a stack.

 

Download   Run Complete Code

 

5. Make head reference global

We can construct a linked list by making the head reference global but this approach is not recommended since global variables are usually considered bad practice.

 

Download   Run Complete Code

 

6. Return head node

Another common approach many programmers follow is to return the head node from the push() function and update head in the caller. This is illustrated below:

 

Download   Run Complete Code

 
References: http://cslibrary.stanford.edu/103/LinkedListBasics.pdf

 
1 Star2 Stars3 Stars4 Stars5 Stars (1 votes, average: 5.00 out of 5)

Loading...

Thanks for reading.

Please use ideone to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂
 


Leave a Reply

avatar
  Subscribe  
Notify of