Linked Lists

Linked Lists

• List is a collection of elements in sequential order. In memory we can store the list in two ways, one way is we can store the elements in sequential memory locations. This is known as arrays. And the other way is, we can use pointers or links to associate the elements sequentially. This known as Linked Lists. Following Fig. 5.1.1 represents this idea of List.

Definition of linked list :

• A linked list is a linear data structure in which elements are stored in nodes and each node contains:

i) Data and

ii) A pointer/reference to the next node in the sequence.

• In ADT the implementation details are hidden. Hence the ADT will be –

AbstractDataType List

{

Instances : List is a collection of elements which are arranged in a linear manner.

Operations : Various operations that can be carried out on list are ‒

1. Insertion : This operation is for insertion of element in the list.

2. Deletion : This operation removed the element from the list.

3. Searching : Based on the value of the key element the desired element can be searched.

4. Modification : The value of the specific element can be changed without changing its location.

5. Display : The list can be displayed in forward or in backward manner.

}

Review Question

1. Explain list ADT.