List ADT

List ADT

• 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. 3.3.1 represents this idea of List.

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

• The List can be implemented by two ways -

1. Array based implementation

2. Linked List based implementation

Let us discuss these in detail.