Data Structure and Algorithms(Linked List)
- December 23, 2019
- Posted by: sujan Mukherjee
- Category: Data Structure
DATA STRUCTURE – LINKED LIST
So this is a Introduction to Linked List in Data Structure. The linked list data structure is often used to implement other data structures.
Therefore linked list is a sequence of nodes where each node stores its own data and a pointer (address) to the location of the next node.
However Linked List is itself a Data Structure and it is used to implement other
One node links to another forming what can be thought of as a linked chain:
The last item in the list has a link to NULL, indicating the end of the chain.
TYPES OF LINKED LIST
There are 3 types of LINKED List –
- Singly LINKED LIST
- Doubly LINKED LIST
- Circular LINKED LIST
However a linked list is similar to an array, it is not restricted to a declared number of elements. Additionally, unlike an array which stores data contiguously in memory or on disk, a linked list can easily insert or remove elements without reallocation or reorganization of the entire structure because the data items need not be stored contiguously.
LINKED LIST DRAWBACKS
1) Random access is not allowed. We must access nodes sequentially starting from the first one. Therefore, we cannot do a binary search on a linked list, however we can do linear searching.
2) Extra memory space for a link is required for each element of the list.
Applications of linked list in computer science –
- Implementation of stacks and queues
- Implementation of graphs : Adjacency list representation of graphs is most popular which is uses linked list to store adjacent vertices.
- Dynamic memory allocation : We use linked list of free blocks.
- Maintaining directory of names
- Performing arithmetic operations on long integers
- Manipulation of polynomials by storing constants in the node of linked list
- representing sparse matrices
So this was the introduction to Linked List however there is a lot to learn in this Linked List Part