Lists

Specification

AbstractDataType  LinearList{ 
  instances 
    finite ordered collection of elements 
  operations 
    create():   create an empty list 
    destroy(): 
    IsEmpty() 
    Length(): 
    Find(k):    find k'th element 
    Search(x):  find position of x 
    delete(): 
    insert(x): insert x after the current element element 
    output(): 
} 

Array Representation

• Operations require simple implementations.
• Insert, delete, and search, require linear time
• Inefficient use of space

One-way Linked Representation

• Insert and delete in O(1) time
• Search in O(n) time
• Memory overhead, but allocated only to entries that are present.

Circular One-way Linked Representation

• The head node, together with the circular representation, simplify the dealing with boundaries conditions

Doubly Linked Representation

• Insert and delete in (1) time.
• We can also go here for doubly linked list with an additional header node.