Definitions of various ADTs

adt.md

Abstract Data Types (ADTs)

---

List

A collection of elements.

Operations

Unary

• Insertion of element e into the ith position of the list
  • insert(e, i)
• Removal of element at the ith position in the list
  • remove(i)

Example,

Starting with the empty list []:

• insert(1, 0) yields [1]
• insert(3, 1) yields [1, 3]
• insert(5, 2) yields [1, 3, 5]
• insert(2, 1) yields [1, 2, 3, 5]
• remove(2) yields [1, 2, 5]

Binary

• Concatenation of lists
  • L = concatenate(L1, L2)

Example,

• concatenate([1, 2, 5], [1, 3, 8]) = [1, 2, 5, 1, 3, 8]

Access

• Get element at the ith position of the list
  • get(i)
• Set element at the ith position of the list to the value e
  • set(e, i)

Size

• Length
  • Total number of elements in the list

Equality

Two lists, L1, L2, are equal iff.:

1. L1 and L2 have the same elements
2. L1 and L2 have the same ordering of elements

Example,

• [1, 2, 3] == [1, 2, 3]
• [1, 2, 3] != [1, 3, 2]
• [1, 1, 1, 2] != [1, 2]

Membership

A list L' is a sublist of the list L iff.:

1. L' has at least one element that is also in L
2. L' has the same ordering of these elements as the elements in L

Example,

• [1, 2, 3] is a sublist of [1, 2, 3, 4]
• [] is a sublist of every list
• [1] is a sublist of [1, 2]
• [1] is a sublist of [1]
• [2, 3] is not a sublist of [1, 3, 2]
• [1, 1, 1, 1, 1] is not a sublist of [1, 2, 3]

Stack

A collection of elements.

Operations

Unary

• Push element e onto the top of the stack
  • push(e)
• Pop element at the top of the stack off of the stack
  • pop()

Example,

Starting with the empty stack []:

• push(1) yields [1]
• push(2) yields [2, 1]
• push(3) yields [3, 2, 1]
• pop() yields [2, 1]
• push(4) yields [4, 2, 1]

Access

• Get the element at the top of the stack
  • peek()

Size

• Height
  • The total number of elements in the stack

Equality

Two stacks, S1, S2, are equal iff.:

1. S1 and S2 have the same elements
2. S1 and S2 have the same ordering of elements

Example,

• [1, 2, 3] == [1, 2, 3]
• [1, 2, 3] != [1, 3, 2]
• [1, 1, 1, 2] != [1, 2]

Membership

A stack S' is a substack of the stack S iff.:

1. S' has at least one element that is also in S
2. S' has the same ordering of these elements as the elements in S

Example,

• [1, 2, 3] is a substack of [1, 2, 3, 4]
• [] is a substack of every stack
• [1] is a substack of [1, 2]
• [1] is a substack of [1]
• [2, 3] is not a substack of [1, 3, 2]
• [1, 1, 1, 1, 1] is not a substack of [1, 2, 3]

Queue

A collection of elements.

Operations

Unary

• Push element e onto the back of the queue
  • push(e)
• Pop the element at the front of the queue off of the queue
  • pop()

Example,

Starting with the empty queue []:

• push(1) yields [1]
• push(2) yields [1, 2]
• push(3) yields [1, 2, 3]
• pop() yields [2, 3]
• pop() yields [3]

Access

• Get the element at the front of the queue
  • peek()

Size

• Length
  • The total number of elements in the queue

Equality

Two queues, Q1, Q2, are equal iff.:

1. Q1 and Q2 have the same elements
2. Q1 and Q2 have the same ordering of elements

Example,

• [1, 2, 3] == [1, 2, 3]
• [1, 2, 3] != [1, 3, 2]
• [1, 1, 1, 2] != [1, 2]

Membership

A queue Q' is a subqueue of the queue Q iff.:

1. Q' has at least one element that is also in Q
2. Q' has the same ordering of these elements as the elements in Q

Example,

• [1, 2, 3] is a subqueue of [1, 2, 3, 4]
• [] is a subqueue of every queue
• [1] is a subqueue of [1, 2]
• [1] is a subqueue of [1]
• [2, 3] is not a subqueue of [1, 3, 2]
• [1, 1, 1, 1, 1] is not a subqueue of [1, 2, 3]

Set

A collection of elements that does not allow repetition (i.e. every element of the collection is unique) and is unordered.

Operations

Unary

• Add the element e to the set
  • add(e)
• Remove the element e from the set
  • remove(e)

Example,

Starting with the empty set, {}:

• add(1) yields {1}
• add(1) yields {1}
• remove(1) yields {}

Binary

• Intersection of sets
  • S = intersect(S1, S2)
• Union of sets
  • S = union(S1, S2)
• Difference of sets
  • S = difference(S1, S2)

Example,

• intersect({1, 2, 3, 4}, {3, 4, 5, 6}) = {3, 4}
• union({1, 2, 3}, {4, 5, 6}) = {1, 2, 3, 4, 5, 6}
• difference({1, 2, 3}, {3, 4, 5}) = {1, 2}

Size

• Carindality
  • The total number of elements in the set

Equality

Two sets, S1, S2, are equal iff.:

1. S1 and S2 have the same elements

A corrollary of this is that both sets are subsets of each other.

Example,

• {1, 2, 3} == {1, 2, 3}
• {3, 2, 1} == {2, 3, 1} == {1, 2, 3}
• {} != {0}
• {1, 1, 1, 1, 1, 2} == {1, 2}

Membership

A set S' is a subset of the set S iff.:

1. If an element e is in S', it is also in S

Example,

• {} is a subset of every set
• Every set is a subset of itself
• {1} is a subset of {1, 2}
• {1, 2, 3} is a subset of {3, 2, 1}
• {1, 2, 3} is not a subset of {1, 2, 4}

Multiset

A collection of elements that is unordered.

Operations

Unary

• Add the element e to the multiset
  • add(e)
• Remove the element e from the multiset
  • remove(e)

Example,

Starting with the empty multiset, {}:

• add(1) yields {1}
• add(1) yields {1, 1}
• add(1) yields {1, 1, 1}
• add (2) yields {1, 1, 1, 2}
• remove(1) yields {1, 1, 2}
• remove(2) yields {1, 1}

Binary

• Intersection of multisets
  • insersect(M1, M2)
• Union of multisets
  • union(M1, M2)
• Difference of multisets
  • difference(M1, M2)

Size

• Cardinality
  • Total number of elements in multiset
• Multiplicity
  • The number of times a given element occurs in the multiset

Equality

Two multisets, M1, M2, are equal iff.:

1. M1 and M2 have the same elements
2. M1 and M2 have the same multiplicities of these elements

Example,

• {1, 1, 2, 3} == {3, 1, 2, 1}
• {1, 2, 3} != {1, 1, 2, 3}
• {1} != {1, 1}

Membership

A multiset M' is a submultiset of the set M iff.:

1. If an element e is in M', it is also in M

Example,

• {} is a submultiset of every multiset
• Every multiset is a submultiset of itself
• {1} is a submultiset of {1, 2}
• {1, 2, 3} is a submultiset of {1, 1, 3, 2}
• {1, 2, 3} is not a submultiset of {1, 2, 4}