# Introduction to Linked List

In this article, we are going to learn about the **introduction to linked list**, **linked list as an ADT**, **advantage of linked list**.

Submitted by Radib Kar, on October 14, 2018

## What is linked list?

A linked list is a data structure used for storing 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 program execution.
- Can be made as long as needed. (Until system memory exhausts).
- Doesn’t waste memory space but takes some extra memory for pointers. It allocates memory as it grows.

### Link list as an ADT

Link list is an ADT and has the following operations:

Main link list ADT operation:

**Insert:**Insert element to the list**Delete:**deletes element from the list

Auxiliary link list ADT operations:

**Delete list:**delete and remove the whole list**Count:**returns the number of elements in the list**Find n**Returns the nth node from the beginning of the list^{th}node:

### Why Link list?

There are so many data structure all serves the same purpose like link list. So it must come in mind that why link list, not the others.

Before discussing link list it’s necessary to differentiate link list and array. Both are used for same purpose, but we need to differentiate their usage, their operations. That means where using array is suitable and where linked list.

### Comparison between array and linklist

**Advantage of Arrays:**

- Simple and easy to use
- Faster access to elements (O (1))

**Disadvantage of Arrays:**

- Wastage of memory as indices may be empty.
- Fixed size - Size of array is static.
- To insert an element at a given position, operation is complex. We may need to shift the existing elements to create vacancy to insert the new element at desired position.

However, problem arising for static array can be overcome through dynamic array.

**Advantage of link lists:**

- Can be expanded at constant time, which is expensive for an array
- No wastage of memory
- Insertion at desired position is relatively easier that inserting in an array

**Disadvantage of link lists:**

- The main disadvantage is that the access time for any single element in a link list is not constant like an array.
- Link list somehow needs additional code to be implemented.

**Comparison between link list, array & dynamic array**

Parameter | Link list | Array | Dynamic array |
---|---|---|---|

Indexing | O(N) | O(1) | O(1) |

Insertion/deletion at beginning | O(1) | O(N)(array not full) | O(N) |

Insertion at the end | O(N) | O(1)(array not full) | O(1)... array not full O(N)... array full |

Deletion at the end | O(N) | O(1) | O(N) |

Insertion in the middle | O(N) | O(N)(array not full) | O(N) |

Deletion in the middle | O(N) | O(N)(array not full) | O(N) |

Wasted space | For pointers | For empty indices | Depends on allocation |

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions