Linked data structures, though they sound to be quite simple but are quite difficult to be understood and implement. Here we discuss about the various types of linked data structures that are available. The most common ones are the linked lists and search trees.
About Linked List – a type of linked data structure
– A linked list is defined as a data structure consisting of nodes or data records which ordered by their logical links rather than being ordered by their physical placement.
– These logical links are stored along with the data records as their part.
– Storing them in the adjacent memory locations has not been recognized as an important thing.
– In linked list, every data record has got two fields, one for storing the information and the other one for storing the pointer i.e., the address field.
– The address of the successor node is stored in this address field only.
Linked lists are sub divided in to 3 types namely:
1. Singly linked list
2. Doubly linked list
3. Multiply linked list
There is another way of classifying the linked lists based up on the way it is implemented or representation namely:
1. Linear linked list and
2. Circular linked list
Properties of Linked Lists
Below mentioned are some basic properties associated with the linked lists:
1. The nodes or the objects are linked in a sequence that is linear.
2. It is necessary to keep a reference to the first node in any list. This reference is usually called as front or the head.
– In a singly linked list, each node consists of only one pointer field whereas a node in a doubly linked list consist of two pointer fields for moving in either directions.
– However, in the circular linked list first and the last node are linked together.
– Here, the traversal can be started from any node and the list is followed until the original node is reached.
– This type of linked list is particularly useful when an access to all other objects is required.
– A list when implemented this way can make the iteration process quite difficult.
About Search Trees – a type of linked data structure
– In search trees, the data records or the nodes are stored in some sort of ordered set.
– The data values are ordered such that the traversal of the nodes comes in an ascending order of the data values contained in them.
– Search trees also have certain properties associated with them:
1. The nodes or the objects are to be stored in an ordered set.
2. An ascending read out of the data values should be obtained when in – order traversal is carried out on the tree.
3. The sub trees of a tree are also trees in themselves.
Other Types of Linked Data Structures
– There are many other linked data structures which are derived from the linked lists such as the stack, queue and trees.
– Stack is like an array but has nodes which can be deleted and added only from one end i.e., at the top of the stack.
– A queue is also a linked list which has two ends one front and the other one called rear. Any item to deleted is deleted from the first end and insertions are made at the rear end.
– The stack is considered to be a LIFO (last in first out) list whereas a queue is just the opposite i.e., it is a FIFO (first in first out) list.
– Infinite number of nodes can be inserted in to a linked list whereas the other data structures need to be re-sized since at some stage they will fill up.
– Doubly linked lists take up more space than the single ones.
– Also the operations up on doubly linked lists prove to be quite costly but the access to elements located in either direction becomes easy.
– For the circular representations it is not required to declare a header node.