Linked List part 1
Linked List
BASICS FOR ALGORITHM 2
Part 1
We use different data structures to facilitate Searching, Sorting and Storage of data. Some of the Data Structures which we will be learning today is Introduction to Linked List.
1. Singly Linked list
2. Doubly Linked list
Brief: In this blog post, we will be learning about Linked list, what are they and we will be seeing in brief about singly linked list and doubly linked list. For operations on singly linked list and doubly linked list refer to part 2 of Linked List, Basics for algorithm 2
1. Singly Linked list
2. Doubly Linked list
Brief: In this blog post, we will be learning about Linked list, what are they and we will be seeing in brief about singly linked list and doubly linked list. For operations on singly linked list and doubly linked list refer to part 2 of Linked List, Basics for algorithm 2
Why do we need linked list when we have arrays?
Before talking about Linked list, lets start with arrays. Arrays are a static data structure. we need to specify how much space we will be required before the actual storage of data due to which a lot of memory space is either wasted or is insufficient if the data to be stored is less or more respectively.
due to this constraint of Arrays, we use Linked list. Linked list are dynamic in nature, we can add how much storage we require when needed, at runtime. Even though arrays are static, they have an advantage of access in constant time, or direct access which is not the case in linked list. In Linked list we have to search for the record in a linear way, One after another until we find the required data. Hence, to facilitate the storage and retrieval of data, we use the data structure linked list.
Basic Types of Linked List:
There are several types of linked list available, we will be covering 4 of them. Singly Linked list, Doubly Linked list , Circular Linked List and Multiply linked list.
Linked List:- Linked list are linear sequencing of data in a logical way. i.e. Linked list are not something which is in a sequence when seen in memory but they are connected to each other sequentially using the data structure (pointers).
https://en.wikipedia.org/wiki/Linked_list
https://www.geeksforgeeks.org/data-structures/linked-list/
Basic Types of Linked List:
There are several types of linked list available, we will be covering 4 of them. Singly Linked list, Doubly Linked list , Circular Linked List and Multiply linked list.
Linked List:- Linked list are linear sequencing of data in a logical way. i.e. Linked list are not something which is in a sequence when seen in memory but they are connected to each other sequentially using the data structure (pointers).
fig(a)
Array vs Linked list
By seeing the figure a, we will understand what linked list actually is. take a look at the linked list part, Item 1 points to item 2, while item 2 points to item 3 and so on but they are not sequentially arranged in the memory using these pointers we can easily construct any type of linked list data structure.
Singly Linked List:-
Singly Linked list are linked list with only one pointer in each node, each pointer element points the next node in the list.
fig(b)
Singly linked list
In singly linked list we have additional one pointer namely first pointer or start pointer, the first pointer points the first node in the linked list. the pointer in the last node points to null. i.e it points to nothing, its value is null. (Shown as grounded in fig(b)).
Doubly Linked List:-
In doubly linked list, we have two pointers instead of one pointer, out of which the first pointer points the next node location while the second pointer points the location of previous node. using doubly linked list we can trace in forward as well as in backward direction. a notable disadvantage of using doubly linked list is usage of extra memory due to an additional pointer in each node.
fig(c)
Doubly linked list
The first node in doubly linked list have its previous pointer pointed to null similarly the last node in doubly linked list have its next node pointer pointed to null. We have two additional pointers, namely first pointer , pointing the first node while second pointer namely last stores the address of the last node.
Written by ,
Sarvesh Bhatnagar
Reference:
https://en.wikipedia.org/wiki/Linked_list
https://www.geeksforgeeks.org/data-structures/linked-list/
