Data Structures - List ADT

<< Previous

Next >>

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).
Here A1 is the first element of list and AN is the last element of list. The predecessor of A1 and successor of AN will not be defined. For our convenience, we can assume that the elements in the list are integers.

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

The 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.

Fig 1.Linked List

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

It 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 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.

Fig 2. Singly Linked List

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.

Fig 3. Doubly Linked List

Circular Linked List

It 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.

Fig 4.Circular Linked List

<< Previous

Next >>

Learn about Operating System © 2017