Linear Data Structures - Week 2

Give examples of primitive data types

int, byte, short, float, double

Why is a list an ADT (Abstract Data Type)?

Because we can make a list of any data type

Give one way a list can be represented

Through a (1D) array, accessed by the appropriate memory location.

Organisation of lists

Ordered, linear, random access

What do each of the common operations do for a list?

Insert(v,i)

Delete(i)

Lookup(i)

Search(v)

Length()

Insert element v at position i
Delete element at position i
Return the value of element i
Find the index of an element equal to v
Return the number of elements in the list

Advantages of lists

→ Direct access to element given index (constant time)
→ Efficient memory space (only the elements themselves are stored)
→ Memory locality (all data in one place helps memory access speed)

Disadvantages of lists

→ Inserting and deleting elements difficult
→ Insertion at end uses memory at specific location which may not be available
→ Insertion at other locations must move rest of list

What is a linked list an alternative to?

An array

What does the link do in a linked list?

Indicates where the nex item is in memory

How would item 3 be accessed in a linked list?

Moving through linearly: start at the Head and follow next 3 times.

Advantages of a linked list

→ Inserting and deleting elements easy
→ No moving of data, new items can be anywhere in memory

Disadvantages of a linked list

→ Lists must be scanned to locate elements
→ Extra memory for links
→ Non-locality in memory, may increase access time

What does a doubly linked list do?

Contains an additional link to the previous item, allowing us to traverse the list in either direction. It also stores head (first) and tail (last) so you can traverse from the end.

In terms of a stack:
Type of data structure
What is accessed
How it is implemented
Time complexity

→ Last-in, first-out (LIFO)
→ Can only access top item
→ Implemented as a list, top is last item
→ All operations have the time complexity of O(1) as a contigous array

Organisation of a stack

Ordered, linear, access top element only

What do each of the common operations do in a stack?

Push(v)
Pop()
Top()
Depth()

(s) → (s,v) add v to top of the stack
(s,v) → (s) remove v from top and return it
(s,v) return v
return the number of elements in the stack

What do enqueue and dequeue do in a queue?

enqueue → items are added at the rear
dequeue → items are removed from the front

In terms of a queue:
Type of data structure
What is accessed
How it is implemented
Time complexity

First-in first-out data structure
Access items at the start, add them to the end
Can be implemented as a list
All operations have a time complexity of O(1), time implemented as a linked list

Organisation of a queue

Ordered, linear, access first item only

What do each of the common operations do in a queue?

Enqueue(v)
Dequeue()
Peek()
Length()
isFull()
isEmpty()

(s) → (s,v) add v to the end of the queue
(v,s) → (s) remove v from start and return it
(v,s) → return v
return the number of elements in the queue
test to see if the queue is full
test to see if the queue is empty

Linear queues

Implemented as an array with pointers at the front and rear

Circular queues

Fills up all spaces in a fixed size array more elegantly (requires extra pointer management)

What can ordering be done on in data types?

Ordering on numeric times
Lexographical ordering (string) based on character set order

Let ≤ be a total order on data type T.
Then ≤ satisifes the total properties with data a and by of type T.
What are its properties?

1. 𝑎 ≤ 𝑎 (reflexive)
2. If 𝑎 ≤ 𝑏 and 𝑏 ≤ 𝑐 then 𝑎 ≤ 𝑐
(transitive)
3. If 𝑎 ≤ 𝑏 and 𝑏 ≤ 𝑎 then 𝑎 = 𝑏
(antisymmetric)
4. 𝑎 ≤ 𝑏 or 𝑏 ≤ 𝑎 (strongly connected)

If our data has a total order and is in a
list, we can sort it.
Sorted data (in ascending order) has
the property that ∀𝑖, 𝑗, 𝑖 ≤ 𝑗 ⇔ 𝑙(𝑖) ≤ 𝑙(𝑗)

What does this mean for 2 orders?

The first ≤ is the usual order on integers.
The second is the total order on T

For the relation: ‘Family tree relation, ‘ancestor of’ (you are taken to be your own ancestor)’ why is it not a total order?

Alice is an ancestor of Alice (reflexive & anti-symmetric)

Alice is an ancestor of Bob & Bob is an ancestor of David, therefore Alice is an ancestor of David (transitive)

Charlie is not an ancestor of Bob and Bob is not an ancestor of Charlie, therefore it is not strongly connected

In general, the leaves of this tree have a partial order, cannot be ordered without more info.