LinkedList Basics

A LinkedList data structure is a list of nodes that reference each other by links. Each node stores its own data and has a reference to the next node. The stored data can be of a primitive data type such as integers, character or customized data types such as Invoice, Account etc. Below depiction shows a Linked List, where each node contains an Integer data (i.e. the data in first node is 11) and a link to the next node’s location. The arrow between nodes denotes a link to the next node.

11 -> 23 -> 16 -> 19 -> 54

LinkedLists are commonly used in cases where there are frequent insertions and deletion of data in the list and where data set size (ie. maximum number of nodes) is not known. For example, web browser history can be stored using LinkedLists as shown in example below:

P1, P2 in below image indicate webpages that the user visited using the browser. The browsing history is being tracked via a LinkedList. The user first visits following pages:

P1 -> P2 -> P3 -> P4 -> P5

From webpage P5 the user navigates back to webpage P3 using the back button twice. From webpage P3 the user navigates to webpages P6 and P7. At this point in time, links to P4 and P5 need to deleted from the browser history LinkedList and new nodes for P6 and P7 need to be added to the LinkedList.

P1 -> P2 ->P3 -> P6 ->P7

LinkedLists are different from the concept of arrays. In arrays, the data nodes are stored adjacent to each other in the memory allocated for the array. But in LinkedLists, the nodes may not be stored adjacent/ next to the previous node. In a LinkedList, each node contains a link to the next node’s location. The memory location of the nodes need not be adjacent as is in the case of an array. Below image shows an array of size 5, with different integer data in each slot. Each data is stored adjacent to other data in memory space allocated to the array.


11	23	16	19	54

LinkedLists Vs Arrays in terms of memory usage.

Array size (i.e. number of nodes / data that can be stored in array) is fixed and is decided at compile time. If Array of size 5 is declared, only 5 maximum data elements can be stored in it at a time. LinkedList size is not declared at time of initialization; you can add the first element and then keep on adding elements (limited only by maximum memory available in the machine).

In Arrays, memory is reserved as per array size declared. If array of size 5 is declared, memory for 5 elements will be reserved, even if you store 1 data element. In case of LinkedList, the memory is allocated on need basis. If LinkedList has only one node, only memory required for 1 node will be utilized, if there are n nodes, then memory required for n nodes will be utilized.

Array elements are stored contiguously in memory. LinkedList nodes may not be stored contiguously in memory, if we have reference to first node of LinkedList, we can access all the other nodes via “next” links.

LinkedLists Vs Arrays in terms of time complexity in accessing data elements.

Arrays have an array index which allow direct access to element in array if the index is known. Time complexity for accessing an element in an array is O(1), because we need only 1 access of memory location to access any element in an array if we know the index at which the data is located. In Linked Lists, Time complexity for accessing any random element in the Linked List is O(n) on average, because we do not have direct access to the required node in Linked List. Each node is accessible only via next link of previous node. So, on an average n access may be required to access a required node in a Linked list having n nodes.

• For Insertion and deletion of nodes in an Array the Time complexity is O(n) on average, as we may have to move existing array elements to insert a new element in array. On the other hand Time complexity for addition or deletion of a node in Linked List is O(1).

Use cases for LinkedLists

When the maximum count of data to be stored in list is not known.

Where frequent additions/deletions are done to the data list, and O(1) access time is require for these addition/deletion operations.

In use cases where O(n) average access time is acceptable to access a random element in the list of data, LinkedList can be used.

Time Complexity of Java LinkedList operations

Following table shows time complexity metrics for Single LinkedList operations

Operation	Complexity
Add operation (First Node).	O(1)
Add operation (Any middle node).	O(n)
Remove/Delete operation (First Node).	O(1)
Delete operation (Any middle node).	O(n)
Search/Contains/lookup operation.	O(n)
Get size of LinkedList.	O(n)

Types of LinkedLists.

There are three main types of Linked Lists: SingleLinkedList, DoubleLinkedList, CircularLinkedList. In the next sections we will study these three types of LinkedLists in detail. Conceptual design of these LinkedLists along with main operations like initialization/addition/ deletion of elements to Linked Lists and code challenges are provided in sections below.

LinkedList in Java JDK API.

Java provides LinkedList class, which is implemented as a doubly linked list. It provides several methods to add, remove, get, check containership. For learning purposes, we will use our own implementation of LinkedLists, but readers should always keep in mind that LinkedList class already exists in Java and it should be used, whenever it meets the requirements.