Abstract Data Types Notes

Posted on Edited on In , Views: Disqus:

List

Lists provide one natural implementation of stacks, and are the data structure of choice in many places where flexible representation of variable amount of data is wanted.

Doubly-linked list

A feature of lists is that, from one item, you can progress along the list in one direction very easily; but once you have taken the next of a list, there is no way of returning. To make it possible to traverse a list in both directions one might define a new type called Doubly Linked List in which each wagon had both a next and a previous pointer.
$$
w.next.previous == w
$$
Equation (1) would hold for every wagon inside the DLL except for the last
$$
w.previous.next == w
$$
Euqation (2) would hold for every wagon inside the DLL except for the first.

Graph representation (using List)

Represent each vertex by an integer, and having a vector such that element $i$ in the vector holds the head of a list of all the vertices connected directly to edges radiating from vertex $i$.

ADT List

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
ADT List {
	boolean isEmpty();
	// BEHAVIOUR: Return true iff the structure is empty
	item head();
	// PRECONDITION: isEmpty()==false
	// BEHAVIOR: return the first elemnet of the list (without removing it)
	void prepend(ite x);
	// BEHAVIOUR: add element <x> to the beginning of the list.
	// POSTCONDITION: isEmpty()==false
	// BAHAVIOUR: head() == x
	List tail();
	// PRECONDITION: isEmpty()==false
	// BEHAVIOUR: return the list of all the elements except the first (without removing it).
	
	void setTail(List newTail);
	// PRECONDITION: isEmpty()==false
	// BEHAVIOUR: replace the tail of this list with <newTail>.
}

Stack

  • LIFO (last in first out)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
ADT Stack {
	boolean isEmpty();
	// BEHAVIOUR: return true iff the structure is empty
	void push(item x);
	// BEHAVIOUR: add element <x> to the top of the stack
	// POSTCONDITION: isEmpty()==false.
	// POSTCONDITION: top()==x
	item pop();
	// PRECONDITION: isEmpty()==false
	// BEHAVIOUR: return the element on the top of the stack
	// As a side effect, remove it from the stack.
	item top();
	// PRECONDITION: isEmpty()==false
	// BEHAVIOUR: Return the element on top of the stack (without removing it).
}

Implementations

  1. Combination of an array and an index (pointing to the “top of stack”)
    • The push operation writes a value into the array and increments the index
    • The pop operation delets a value from the array and decrements the index
  2. Linked lists
    • Pushing an item adds an extra cell to the front of a list
    • Popping removes the cell at the front of the list

Use cases

  • Reverse Polish Notation (e.g. 3 12 add 4 mul 2 sub -> (3 x 12) x 4 - 2)

Queue and Deque

  • FIFO (first in first out)
1
2
3
4
5
6
7
8
9
10
11
12
13
ADT Queue{
	boolean isEmpty();
	// BEHAVIOUR: return true iff the structure is empty.
	void put(item x);
	// BEHAVIOUR: insert element <x> at the end of the queue.
  // POSTCONDITION: isEmpty()==false
  item get();
  // PRECONDITION: isEmpty()==false
  // BEHAVIOUR: return the first elemnt of the queue, and removing it from the queue
  item first();
  // PRECONDITION: isEmpty()==false
  // BEHAVIOUR: return the first element of the queue without removing it
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
ADT Queue{
	boolean isEmpty();
	// BEHAVIOUR: return true iff the structure is empty.
	void putFront(item x);
	// BEHAVIOUR: insert element <x> at the front of the queue.
  // POSTCONDITION: isEmpty()==false
  void putRear(item x);
  // BEHAVIOUR: insert element <x> at the back of the queue.
  // POSTCONDITION: isEmpty()==false
  item getFront();
  // PRECONDITION: isEmpty()==false
  // BEHAVIOUR: return the first elemnt of the queue
  item getRear();
  // PRECONDITION: isEmpty()==false
  // BEHAVIOUR: return the last element of the queue 
}

Dictionary

  • Also known as Maps, Tables, Associative arrays, or Symbol tables
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
ADT Dictionary {
	void set(Key k, Value v);
 	// BEHAVIOUR: store the given (<k>, <v>) pair in the dictionary.
	// If a pair with the same <k> had already been stored, the old
	// value is overwritten and lost.
	// POSTCONDITION: get(k) == v

	Value get(Key k);
	// PRECONDITION: a pair with the sought key <k> is in the dictionary.
	// BEHAVIOUR: return the value associated with the supplied <k>,
  // without removing it from the dictionary.
	
	 void delete(Key k);
	 // PRECONDITION: a pair with the given key <k> has already been inserted.
	 // BEHAVIOUR: remove from the dictionary the key-value pair indexed by
	 // the given <k>.
}