An ADT is a set of objects together with a set of operations to process the objects.
One and the same set of objects may be defined with different sets of operations,
and then we will have different ADTs.

ADTs are implemented using classes, thus the implementational details
are hidden from the application programs.

Definition: A linear configuration of elements, called nodes.

Characteristics:

• We can insert and delete nodes in any order.
• The nodes are connected.
• Each node has two components:
  Information (data)
  Link to the next node

• The nodes are accessed through the links between them.

For each node the node that is in front of it is called predecessor.
The node that is after it is called successor.

• Head (front, first node): The node without predecessor, the node that starts the lists.
• Tail (end, last node): The node that has no successor, the last node in the list.
• Current node: The node being processed. From the current node we can access the next node.
• Empty list: No nodes exist

Notation:

1. To create/destroy a list

InitList(L)
Procedure to initialize the list L to empty.

DestroyList(L)
Procedure to delete all elements in the list L.

2. To expand/shrink the list

InsertBefore(L,e)
Procedure to insert a node with information e before the current position,
or if L is empty - as the only node in L.
The new node becomes the current node.

Assumptions: There is room. If the list is nonempty, the current position is not empty.

InsertAfter(L,e)
Procedure to insert a node with information e after the current position,
or if L is empty - as the only node in L. In this case the current position indicates the new node.
The current position is not changed.

Assumptions: there is room. If the list is nonempty, the current position is not empty.

Delete(L)
Procedure to delete the current node in L and to have the current position indicate the next node.

Assumptions: the current position is not empty .

3. Read/Write operations

StoreInfo(L,e)
Procedure to update the information part of a node, assuming it is not empty.

RetrieveInfo(L) à e
Function to return the information in the current node. Assume it is not empty.

RetrieveNextInfo(L) à e
Function to return the information in the node after the current node.
Assume the node is not empty, and the next node is not empty
(the current position is not the last node)

4. Changing the current node (moving along the list)

Advance(L)à b
Boolean function to make the current position indicate the next node.
Returns FALSE if the current position is at the last node in the list and advance is not possible.
Assume the current position is non empty in a nonempty list

ToFirst(L)
Procedure to make the first node become the current node.
If the list is empty, the current position remains empty.

5. To report where we are in the list

AtFirst(L) à b
Boolean function. Returns TRUE if the current node is the first node (the head).

AtEnd(L) à b
Boolean function. Returns TRUE if the current node is the last node (the tail)
6. To report status of the list

ListEmpty(L)à b
Returns TRUE if the list is empty

ListFull(L)à b
Returns TRUE if the list is full (for dynamic implementation it is always
FALSE - the list 'never' becomes full)

CurlsEmpty(L) à b
Returns TRUE if the current position is empty.

To insert a node X between nodes A and B:.

1. Create a link from X to B.
2. Create a link from A to X.

To delete a node X between A and B:

1. Create a link from A to B.
2. Remove node X

Node linking

1. Single linked lists: Each node contains a link only to the next node
2. Double linked lists: Each node contains two links - to the previous and to the next node.
3. Circular lists: The tail is linked to the head.

Two ways to implement a list:

Two parallel arrays are used:

• Index array - the number stored in the i-th element shows the index of the "next" node
• Data array - used to store the informational part of the nodes.

Data[0] corresponds to the head of the list.

Data [i] holds list elements, i > 0

Index[i] holds the position in the Data array where the next node of Data[i] is stored.

In this diagram, the fourth element in the Data array is a node that contains the letter "A".
Its corresponding fourth element in the Index array contains 3 -

Definition: A sequence of elements of same type.
The last stored element is the first to be accessed.
The structure is known also under the name LIFO - last in first out

Notation:

A procedure to replace the elements of a nonempty stack with their sum,
assuming they are of type integers,

Pre: A nonempty stack with elements of type integers.

Post: S contains only one element - the sum of previously stored elements.

1. element1 ¬ pop(S)
2. while stack is not empty repeat the following

2.1. element2 ¬ pop(S)


2.2. push(S,element1+element2)

2.3. element1 ¬ pop(S)

3. push(S,element1)