# 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 |

Related Tutorials

- Structured Programming, its Advantages and Disadvantages
- Data Structure types and operations associated with them
- Introduction of Data Structure
- Linear, Binary & Interpolation search
- Array Data Structure
- Single Linked list and its basic operations with traversing implementation
- Single linked list insertion
- Single linked list deletion
- Deleting a node from a linked list without head pointer
- Implement union and intersection of two sorted linked lists
- Stack
- Implement of stack using array
- Implementation of Multi Stack in C
- Nesting of parentheses using stack

- Check for balanced parentheses by using Stacks (C++ program)
- Double Stack
- Implementation of Stack using two Queues
- Linear Queue
- Circular Queue
- Double Ended Queue (DeQueue)
- Priority Queue
- Implementation of Queue using two Stacks
- Hashing Data Structure
- Hash functions and its characteristics
- Collisions in Hashing and Collision Resolution Techniques
- Hashing | Separate chaining for collision resolution
- Hashing | Open addressing for collision handling
- Hashing coding problems

Comments and Discussions!