Friday, 24 November 2017

Linked List: A Linear Data Structure

Linked List is a linear data structure in which every element is linked with each other in a sequential manner. Below are some properties of Linked list are given:
1. Linked List is a dynamic data structure.
2. Linked List is a linear collection of data items.
3. In Linear List direction of each element is associated with it.
4. In Linear List logical link exits between items and pointers acts as the logical link.
5. Linked List consists of nodes that has two fields. Data field : info of the element. Next field: next pointer containing the address of next node.

Different types of Linked List:
1. Singly or chain: Single link b/w items.
2. Doubly: There are two links, forward and backward link.
3. Circular: The last node is again linked to the first node. These can be singly circular & doubly circular list.

Different advantages of Linked List:
1. Linked list use dynamic memory allocation thus allocating memory when program is initialised. List can grow and shrink as needed. Arrays follow static memory allocation. Hence there is wastage of space when less elements are declared. There is possibility of overflow too bcoz of fixed amount of storage.
2. Nodes are stored incontiguously thus insertion and deletion operations are easily implemented.
3. Linear data structures like stack and queues are easily implemented using linked list.

Different dis-advantages of Linked List:
1. Wastage of memory as pointers requirextra storage.
2. Nodes are in-contiguously stored thereby increasing time required to access individual elements. To access nth item arrays need a single operation while linked list need to pass through (n-1) items.
3. Nodes must be read in order from beginning as they have inherent sequential access.
4. Reverse traversing is difficult especially in singly linked list. Memory is wasted for allocating space for back pointers in doubly linked list.

Mukesh Rajput

No comments:

Post a Comment

Mukesh Rajput