Linked List Data Structure in Java

Author:
In this article, we will quickly look into what is linked list?, comparison with Arrays, advantage and disadvantages over Arrays and types of linked lists.

What is a Linked List?

A linked list is a data structure used for storing collections of data. A linked list has the following properties.
  • Successive elements are connected by pointers
  • The last element points to NULL
  • Can grow or shrink in size during execution of a program
  • Can be made just as long as required (until systems memory exhausts)
  • Does not waste memory space (but takes some extra memory for pointers). It allocates memory as the list grows.

Linked List Representation

A linked list can be visualized as a chain of nodes, where every node points to the next node.
  • Linked List contains a link element called first.
  • Each link carries a data field(s) and a link field called next.
  • Each link is linked with its next link using its next link.
  • The last link carries a link as null to mark the end of the list.

Difference Between Linked lists and Arrays

As we know that both linked lists and Arrays are used to store collections of data, and since both are used for the same purpose, we need to differentiate their usage. That means in which cases arrays are suitable and in which cases linked lists are suitable.
Let's first briefly look at advantage and disadvantage of Arrays then we will compare Arrays with Linked lists.

Array Overview

  • An array is a container object that holds a fixed number of values of a single type.
  • The length of an array is established when the array is created. After creation, its length is fixed.
  • As we know Array is a data structure where we store similar elements and Array starts from index 0.
  • Each item in an array is called an element, and each element is accessed by its numerical index.
  • Since arrays are objects in Java, we can find their length using member length.
  • A Java array variable can also be declared like other variables with [] after the data type.
  • The variables in the array are ordered and each has an index beginning from 0.
  • Java array can be also be used as a static field, a local variable or a method parameter.
  • The size of an array must be specified by an int value and not long or short.
  • Read more about Arrays on Java Arrays Tutorial

Advantages of Arrays

  • Simple and easy to use
  • Faster access to the elements (constant access)

Disadvantages of Arrays

  • Preallocates: all needed memory up front and wastes memory space for indices in the array that are empty.
  • Fixed size: The size of the array is static (specify the array size before using it).
  • One block allocation: To allocate the array itself at the beginning, sometimes it may not be possible to get the memory for the complete array (if the array size is big).
  • Complex position-based insertion: To insert an element at a given position, we may need to shift the existing elements. This will create a position for us to insert the new element at the desired position. If the position at which we want to add an element is at the beginning, then the shifting operation is more expensive.

Advantages of Linked Lists

The advantage of linked lists is that they can be expanded in constant time. To create an array, we must allocate memory for a certain number of elements. To add more elements to the array when full, we must create a new array and copy the old array into the new array. This can take a lot of time.
We can prevent this by allocating lots of space initially but then we might allocate more than we need and waste memory. With a linked list, we can start with space for just one allocated element and add on new elements easily without the need to do any copying and reallocating.

Disadvantages of Linked Lists

The main disadvantage of linked lists is access time to individual elements. An array is random-access, which means it takes O(1) to access any element in the array. Linked lists take O(n) for access to an element in the list in the worst case.
Another advantage of arrays in access time is a special locality in memory. Arrays are defined as contiguous blocks of memory, and so any array element will be physically near its neighbors. This greatly benefits from modern CPU caching methods.
Although the dynamic allocation of storage is a great advantage, the overhead with storing and retrieving data can make a big difference. Sometimes linked lists are hard to manipulate. If the last item is deleted, the last but one must then have its pointer changed to hold a NULL reference. This requires that the list is traversed to find the last but one link, and its pointer set to a NULL reference.
Finally, linked lists waste memory in terms of extra reference points.

Basic Operations

Following are the basic operations supported by a list.
  1. Insertion − Adds an element at the beginning of the list.
  2. Deletion − Deletes an element at the beginning of the list.
  3. Display − Displays the complete list.
  4. Search − Searches an element using the given key.
  5. Delete − Deletes an element using the given key.

Types of Linked List

Following are the various types of linked list.
  1. Singly Linked List - This list consists of a number of nodes in which each node has a next pointer to the following element. The link of the last node in the list is NULL, which indicates the end of the list.
  2. Doubly Linked List - Items can be navigated forward and backward.
  3. Circular Linked List - Last item contains link of the first element as next and the first element has a link to the last element as previous.

Comments

Post a comment