# What is a 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

**and the**

*head***of collection respectively.**

*tail***is among the simplest and most straightforward**

*LinkedList***, yet pretty efficient and easy to implement.As many other**

*Data Structure***, LinkedList provides common operations such as**

*Data Structures***,**

*insertion***, and**

*deletion***.**

*searching*The main advantage of the ** LinkedList** is in its operations of

**and**

*insertion***. As the**

*deletion***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**

*LinkedList***and**

*insertion***are executed for constant time —**

*deletion***Such performance is achieved by just changing the links of the nodes.**

*O(1).*`public class Node{`

public int value;

public Node next;

public Node(int value){

this.value = value;

this.next = null;

}

}

The basic component of the ** LinkedList** is its

**, or**

*nodes***. Here is a simple implementation of a node. A**

*elements***contains some**

*node***, it may be some number, text or another object, and stores a**

*data***to the next node.**

*reference*`public class LinkedList {`

public Node head;

public Node tail;

public int count;

public LinkedList() {

head = null;

tail = null;

}

}

The ** LinkedList** basically consists of the following structure. It stores the links to the first —

**and last nodes —**

*head***. Whenever a**

*tail***is initialized, it is empty and its head and tail nodes are**

*LinkedList***, that is they have no value. The time complexities of the operations provided by**

*null***are as follows:**

*LinkedList*

Insertion — O (1)

Deletion — O (1)

Search — O (N)

Let’s discuss the operations one by one.

** Insertion** or

**a new node —**

*Adding***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**

*add(node)***. 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**

*tail***and**

*head***of the collection simultaneously. Time complexity of the algorithm is constant time —**

*tail***.**

*O(1)*** Deletion** or

**a node —**

*removing***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**

*remove(node)***. Removing the letter —**

*[a — b — c — b — e]***results in the following collection**

*a***. Importantly, if the**

*[b — c — b — e ]***of the collection is removed, the next item becomes the**

*head***of the collection; or if the**

*head***is removed, the previous node becomes the**

*tail***. Time complexity of the algorithm is constant time —**

*tail***.**

*O(1)*However, the ** LinkedList** is not a solution for all the problems.

**does not provide**

*LinkedList***to**

*fast random-access***, or**

*nodes***, 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**

*elements***takes —**

*searching***time to execute, where**

*O(N)***— the number of nodes in the collection.**

*N*This is the first post in the series of ** Data Structures**. If you are curious to dive deeper and play around with the

**, I recommend to implement the discussed operations by yourself and test.**

*LinkedList*The following are the links for:

Raw classes to implement the LinkedList by yourself

Sample implementation of LinkedList

Test cases