What is a LinkedList?

LinkedList

LinkedList is a linear collection of data where each node, or item in the collection, is linked with the next node. Each node contains some data and has a reference to the next node. The first and last nodes in the collection are called the head and the tail of collection respectively. LinkedList is among the simplest and most straightforward Data Structure, yet pretty efficient and easy to implement.As many other Data Structures, LinkedList provides common operations such as insertion, deletion, and searching.

The main advantage of the LinkedList is in its operations of insertion and deletion. As the LinkedList is stored differently compared to conventional array where the elements are stored contiguously in memory, there is no need to reallocate or reorganize the entire structure at run-time after operations of insertion and deletion. The nodes of the LinkedList are stored randomly in memory and keeping the link to the nodes is enough to access them. Since reallocating or reorganizing the entire structure at run-time is an expensive operation, applying LinkedList in such cases is a good idea. The operations of insertion and deletion are executed for constant time — O(1). Such performance is achieved by just changing the links of the nodes.

The basic component of the LinkedList is its nodes, or elements. Here is a simple implementation of a node. A node contains some data, it may be some number, text or another object, and stores a reference to the next node.

The LinkedList basically consists of the following structure. It stores the links to the first — head and last nodes — tail. Whenever a LinkedList is initialized, it is empty and its head and tail nodes are null, that is they have no value. The time complexities of the operations provided by LinkedList are as follows:

Insertion — O (1)

Deletion — O (1)

Search — O (N)

Let’s discuss the operations one by one.

Inserting a new node

Insertion or Adding a new node — add(node) is implemented pretty straightforwardly. Inserting a new node is possible only in one direction and only into the tail of the collection. Whenever a new node is inserted, the newly added node becomes the tail. The next node after tail is always null, i.e it has no value or it does not exist. Importantly, when the first node is added, the node is the head and tail of the collection simultaneously. Time complexity of the algorithm is constant time — O(1).

Deleting nodes

Deletion or removing a node — remove(node) is implemented in a simple way as well. In order to delete, it is necessary to keep or get the link of the node that is previous to deleting node. Hence, we just change the link of the previous node so that it refers to the next node. As illustrated, may a collection of letters is given [a — b — c — b — e]. Removing the letter — a results in the following collection [b — c — b — e ]. Importantly, if the head of the collection is removed, the next item becomes the head of the collection; or if the tail is removed, the previous node becomes the tail. Time complexity of the algorithm is constant time — O(1).

Searching desired value

However, the LinkedList is not a solution for all the problems. LinkedList does not provide fast random-access to nodes, or elements, of the collection. Hence, it is impossible to get an access to the given element for constant time. To get an access to the desired node or element, it is necessary to iterate over the collection and find it. Ultimately, the operation of searching takes — O(N) time to execute, where N — the number of nodes in the collection.

This is the first post in the series of Data Structures. If you are curious to dive deeper and play around with the LinkedList, I recommend to implement the discussed operations by yourself and test.

The following are the links for:

Raw classes to implement the LinkedList by yourself
Sample implementation of LinkedList
Test cases

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store