Home »
Data Structure
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 nth node: Returns the nth node from the beginning of the list
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 |