# Linked list data structure

Linked list is a very important data structure to understand as lot of problems are asked based on linked list in Amazon, Microsoft and Google interview. Today, we will understand the basics of linked list data structure and it’s implementation.

**Linked list** represent linear sequence of elements. Each element connected to next element using chain of references. Another data structure which store linear sequence of items is array. There are some advantages and uses cases where linked list way of storing sequence is more efficient than array, I will cover that into next post : Arrays Vs Linked lists.

In last paragraph, I emphasized on linkedlist being linear data structure. In * linear data structure*, there is a sequence and order how elements are inserted, arranged and traversed. In order to go to tail of linked list, we have to go through all of the nodes.

* Non linear data structures* are the ones where elements are not arranged or traversed in a specific order. One element may be connected to many others, hence we cannot traverse them in the same order every time. Example of non-linear data structure would be

*maps, dictionaries, trees, graphs etc.*

## Linked list implementation

Linked list consists of node, any number of nodes. Each node contains two things : first, value of the node, this value can be of any type, integer, string, or other user defined type. Second, a reference which points to next node in linked list. A node can be declared as follows:

typedef struct Node { int data; struct Node * next; } Node;

What happens if the node is last node in linked list? At last node, next pointer of the node points to the null. It’s very important to understand this bit, as this condition will be used on almost every problem you have to solve on linked list.

Linked list is dynamic data structure. By dynamic data structure, we mean, it’s size and nature is not defined at the time of compilation, but defined at run time. Every time, a new node is added to linked list, new memory location is allocated and previous node’s next pointer will point to new node.

### Operations of linked list

**Adding node at the end of list**

There are three basic steps to add a node to linked list at end:

- Check if there is already a node
- If no, then create a new node and return it as head of linked list.

- If there is a node,
- Scan through linked list using next pointer, reach to the last node.
- Create a new node, and point next pointer of last node to this new node.

Node * createNode(int val){ Node * newNode = (Node *)malloc(sizeof(Node)); if(newNode){ newNode->data = val; newNode->next = NULL; } return newNode; } void addNode(Node **headRef, int value){ //create new node Node *newNode = createNode(value); //find the last node Node *currentNode = *headRef; while(currentNode && currentNode->next != NULL){ currentNode = currentNode->next; } if(currentNode) currentNode->next = newNode; } else{ //Change headRef to point to new head. *headRef = newNode; } }

Complexity of adding a node to linked list is O(n).

**Insert node at head of list**In this case too, we allocate a new node, however, this time we do not have to scan the entire list. Every time we add node to list, it’s head changes though.

- Check if there is already a node
- If no, then create a new node and return it as head of linked list.

- If there is a node,
- Create a new node, and point next pointer new node to head.
- Return new node as head pointer.

Node * createNode(int val){ Node * newNode = (Node *)malloc(sizeof(Node)); if(newNode){ newNode->data = val; newNode->next = NULL; } return newNode; } void addNode(Node **headRef, int value){ //create new node Node *newNode = createNode(value); newNode->next = *headRef; *headRef = newNode; }

### Linked list data structure problems

It’s very important to understand that linked list is a **recursive data structure.** Base case is a linked list with no node, represented by NULL node. Every problem on linked list can be solved using template : process one node, and then recursively process the remaining linked list.

In programming terms, linked list is divided into two parts, head and tail. The node being processed is called head and rest of the linked list is tail. Tail has the exactly same structure as the original list.

Problems like *merging linked lists, reverse a linked list, find length of linked list* all can be solved using the same template of processing one node and the recursively call function on remaining node.

### Types of linked list

There are three types of linked lists :**1. Singly linked list **

Singly linked lists contain nodes with data and reference, i.e., *next*, which points to the next node in the sequence of nodes. The next pointer of the last node will point to null. In singly linked list you can traverse only in one direction.

**2. Doubly linked list**In a doubly linked list, each node contains two links –

*previous,*which points to the node before current node and

*next,*which points to next node. The

*previous*pointer of the first node and

*next*pointer of the last node will point to null. In doubly linked list, you can traverse it both directions. Two references adds to weight as extra memory is required.

**3. Circular linked list**In circular linked list,

*next*pointer of the last node will point to the first node. A circular linked list can be both singly as well as doubly linked list.

This was all for basics of linked list, I know problems on them are hard to solve but if you look at all the problems, they boil down to one thing : understanding of node and how recursion can be used. In next posts, we will be solving many of these problems and see how we can use these basics.

Please share if there is something wrong or missing. If you are interested in contributing to website and share your knowledge with thousands of users across world, please reach out to us at [email protected]