In: Computer Science
What is a linked data structure?
What is a node?
What are the benefits of linked structure?
What are the drawbacks of linked structure?
What are the differences between singly linked and doubly linked structures?
Give examples of when a linked structure could be used.
1. linked data structure is a data structure where data(nodes)
are linked together to form a linear structure.
The connection beween data is called links hence it is known as
linked data structure.
2. Linked list is a collection of nodes. A node represents a
single entity in a list. A node is connected to other node using
node.next. A node consists of a data element and pointer to the
next node.
3. Benefit of linked data structure is that , It helps us to
perform easy addition and deletion of data .
Just by remving and adding the links we can add and remove the dats
unline array where we have to shift all the array elements if we
delete any element from between.
4. Drawback is that . Randon access of elements in list is slow. We
have to traverse list to find element at 5th/4th/3rd location.
Where as in array we get it using the subscript element like arr[0]
, arr[5].
5. In Singly linked list we can move only in forward direction
because a node is connected to its next node. There is no previous
pointer to a node.
Where as In doubly linked list we can move in forward as well as
backward direction because a node is connected to its next node and
previous node .There is a previous pointer to a node.
struct SinglyLinkedlIst{
int data;
SinglyLinkedlIst * next;
}
struct DoublyLinkedlIst{
int data;
DoublyLinkedlIst *prev, *next;
}
6. Linked list are used to Implement Stack, Queue , Tree etc
Useful in implement graphs using Adjacency List
In dynamic memory management (Malloc etc)
Used in implementing The LRU cache.