Data Structures - List ADT
In this tutorial, Let us learn about List ADT, Linked List, Types of Linked List, Singly Linked List, Doubly Linked List, How to implement a List, Operations available for a List amd Circular Linked List
List is expressed in the form of A1, A2, A3....AN. Hence, the size of this list is N. If size is 0, this special list is called an empty list or null list.
For any list,
- Ai+1 follows (or succeeds) Ai (i>N) and
- Ai-1 precedes Ai (i<1).
List Implementations
List can be implemented using Array or Linked list. Linked list has several types: Singly linked list, Doubly linked list and Circular Linked list.
Linked List
Linked list consists of series of structures or nodes. Each structure or node has two parts, one is data part and another is a pointer to a successor. This pointer is called next pointer. The last structure's next pointer always points to null, indicating that there are no more elements in the linked list. Therefore, the data part can hold an element and pointer part can hold address where the next data is stored. Unlike arrays, in linked list, data elements are stored randomly in memory.
Following are some set of operation that has to be performed on the List ADT.
- Insert - Insert an element into the list.
- Delete - Delete an element from the list.
- Find - Return first occurrence of a key.
- Find kth - Return the kth element
- PrintList - Print the entire List
Types of Linked List
Singly Linked List
Singly Linked List is the linear collection of nodes. Each node is divided into two parts. One is data part which store data element. Another is pointer which holds the address of next node in the list. The head contains starting address of the singly linked list which point to the first element in the list. The operation can be performed on the singly linked list are insertion, deletion and find.
Doubly Linked List
Sometimes, it is convenient to traverse the link on both sides. One solution is doubly linked list. In this case both forward and backward access is possible. It is defined as a series of nodes in which each node indicates the memory spaces. Each node divided into three fields that are data field, next field or forward field and previous or backward field. The data field is used to hold data values. The next or forward field is used to hold address of Next node. The previous or backward field can hold address of previous node. The first node's of previous field and last node's of next field are always NULL.
Circular Linked List
Circular Linked List is defined as series of nodes in which each node can carry a data and address information. In this circular linked list, the last node's next pointer does not have null value. Instead, it has the address which point to the first node.
