@zareen
The Linked List ADT
We have been using linked nodes to generate our structures for the Stack ADT and the Queue ADT. Now we will consider the linked list. As we have been using this structure for implementing the previous ADT structures, it is perhaps more constructive to look at a variation of the single linked list (known as the ‘sorted’ linked list).
The idea behind this type of list is that any element we put into the list will have to be put into the correct position by comparing some common value held in each of the nodes. So far the Stack ADT and the Queue ADT did not impose any ordering on the elements we added. If we were looking for a basic linked list, we could use these as the basis for the structure and operations. This is a task you might attempt for yourselves.
Our sorted linked list ADT will consist of the following primitive operations:
Create()
Destroy()
Add(element)
Remove(element)
Traverse()
IsEmpty()
Search(element)
We would generally need a display operation for testing purposes to ensure that the elements are being put into the correct locations. However, the Sorted linked list is a linear structure so any processing done on the list has to be carried out in a linear manner. We must access the list through the Start link / pointer and the list has to be accessed/processed in the order that the nodes appear on the list.
As we have previously seen, one of the great advantages of the linked data structure is the ease with which it may be modified. Changing the structure does not involve moving the existing nodes. In order to delete a node we update the link / pointer of the node before it and point / link this to the node after it.