In the Linked List Data Structure in Java tutorial, you will learn how to create and perform different operations on a linked list. You will also learn about its applications. A linked list is a linear data structure, in which the elements are not stored at contiguous memory locations. The elements in a linked list are linked using pointers as shown in the below image:
A linked list is a series of connected “nodes” that contains the “address” of the next node. Each node can store a data point which may be a number, a string or any other type of data.
The address of first node in the linkedlist is HEAD. The last node in the linkedlist can be identified because it’s next portion points to NULL.
Why do we need Linked List?
Both of Linked List and Arrays can be used to store linear data structure, but arrays have some limitations:
- The size of arrays is fixed and the allocated memory is equal to the upper limit irrespective of the usage. A Linkded List is a dynamic size and the allocated memory is equal to the real size of usage.
- Inserting a new element in an array of elements is expensive. But it is ease of insertion/deletion with Linked List.
Drawbacks of Linked List
- Random access is not allowed. We must only access nodes sequentially starting from the first node.
- Extra memory space for a pointer of each node in the list.
- Not cache friendly.
- One of the disadvantages of using a linked list to store data is the time necessary to search for an item. Since Linked Lists are linear structures the time required to search a “linear” list is proportional to the size of the data set. This issue is sorted out if we use a nonlinear data structure like a tree data structure.
How another node is referenced in the linkedlist?
A linked list is designed by a pointer to the first node. The first node is called the head. If the linked list is empty, then the value of the head is NULL. Each node in a list consists of at least two parts:
- A data item
- Pointer to the next node
Implement Linked List Data Structure in Java
We might implement the above specification of LinkedList in Java language like this:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
class LinkedList { Node head; // head element /* Linked list Node*/ class Node { int data; // data item Node next; //Next is by default initialized as null // Constructor to create a new node Node(int d) { data = d; next = null; } } } |
Here is a simple program that demonstrates a linked list.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
// A simple Java program to demonstrate a linked list class LinkedList { Node head; // head element /* Linked list Node*/ static class Node { int data; Node next; Node(int d){ data = d; next = null; } } /* traverse the created list and print the data of each node */ public void displayList() { Node n = head; while (n != null) { System.out.print(n.data + ","); n = n.next; } } /*create a simple linked list with 3 nodes*/ public static void main(String[] args) { /* Start with the empty list. */ LinkedList linkedlist = new LinkedList(); linkedlist.head = new Node(10); Node second = new Node(20); Node third = new Node(30); linkedlist.head.next = second; // Link first node with the second node second.next = third; // Link second node with the third node linkedlist.displayList(); } } |
Here is output of the above program
|
1 |
10,20,30, |
That’s all about Linked List Data Structure in Java.
References
Linked List Data Structure in Java
Data Structures and Algorithms Tutorial in Java
