Linked List -Train of nodes
In computer science, a linked list is one of the fundamental dynamic data structures used in computer programming. It consists of a sequence of nodes, each containing arbitrary data fields and one or two references ("links") pointing to the next and/or previous nodes.
Linked lists have their own strengths and weaknesses, but they happen to be strong where arrays are weak. Generally array's allocates the memory for all its elements in one block whereas linked lists use an entirely different strategy. Linked lists allocate memory for each element separately and only when necessary.
A linked list is a self-referential data type because it contains a link to another data of the same type. Linked lists permit insertion and removal of nodes at any point in the list in constant time, but do not allow random access.
If adding and deletion is rare and you will be doing random access a lot, an array is much better. But when you have to update list frequently than a linked list would be preferable.
Advantages of linked lists:
Linked lists are dynamic data structures. i.e., they can grow or shrink during the execution of a program.
Linked lists have efficient memory utilization. Memory is allocated whenever it is required and it is de-allocated (removed) when it is no longer needed.
Insertion and Deletions are easier and efficient. Linked lists provide flexibility in inserting a data item at a specified position and deletion of the data item from the given position.
Many complex applications can be easily carried out with linked lists.
Disadvantages of linked lists:
It consumes more space because every node requires a additional pointer to store address of the next node.
Searching a particular element in list is difficult and also time consuming.
Reverse Traversing is difficult in linked list
Types of Linked Lists:
Basically we can put linked lists into the following...
1. Single Linked List.
2. Circular Single Linked List.
3. Double Linked List.
4. Circular Double Linked List.
5. Header Linked list
6. Multi Linked List.
Applications of linked list:
1. Linked lists are used to represent and manipulate polynomial.
2. Hash tables use linked lists for collission resolution.
3. Any "File Requester" dialog uses a linked list.
4. Linked lists use to implement stack, queue, trees and graphs.
5. To implement the symbol table in compiler construction.
Some common variables use in linked list
START : Store the address of first node.
AVAIL : Store the address of first free space.
PTR : Points to node that is currently being accessed.
NUll : End of list.
NEW_NODE :To store address of newly created node.
0 Comment to "Linked List -Data structures | advantage & disadvantage | Types of linked List"
Post a Comment