Take-Away Notes for Module COMP2048.

Review of Arrays and Linked Lists, Queues, Stacks.

Proofread
Reviewed

Array

Definition

A sequenced collection of variables of the same type, where each variable, or cell, in an array has an unique index as a reference to the value stored.

Length & Capacity

The maximum number of elements that can be stored in the array.

Modification: Add & Remove

To add an element e into array board at index i: 1. Make room by shifting forward the n-i elements data[i], data[i+1], ..., data[n] 2. Add at data[i]

To remove an element e from array board at index i: 1. Shift backward the n-i-1 elements data[i+1], data[i+2], data[n-1]; 2. Since data[i] is replaced/covered, reset data[n] to null to release the allocated memory.

Linked List

Singly Linked List

Definition

A concrete data structure consisting of a sequence of nodes starting from a head pointer, where each nodes stores its own element and the link(reference) to the next node.

Insert at the Head

Allocate new node
Insert new element
Have new node pointed to th old head
Update head to point to the new node

Insert at the Tail

Allocate new node
Insert new element
Have new node point to null
Have old last node point to new node
Update tail to point to the new node

Delete at the Head

Update head to point to the next node
Allow garbage collector to reclaim the former first node

Delete at the Tail

Non-efficient, No constant time-way to update the tail to point to the previous node

Doubly Linked Lists

Definition

A linked list in which each node keeps explicit references to the node before and after it.

Insertion

Allocate new node
Update references to the node before and after
Update the references of the node before and after

Deletion

Update the references of the node before and after
Allow garbage collector to reclaim the node

Queues

Usually use an array of size/capacity of N in a circular fashion.

Update: Full iff sz == N; typo fixed in slides!

Definition

A collection of objects that are inserted and removed according to the FIFO(First In, First Out) rule, that is, insertions are at the rear of the queue and deletion are at the front of the queue.

Keep-Track Constants

f: short-cut for front; index of the 1st element(initialized to 0)
sz: short-cut for size; number of stored elements
r: short-cut for rear; the first empty slot past the rear of the queue;

Modifier

enqueue(obj): inserts an element at the end of the queue
dequeue(): removes and returns the element at the front of the queue ### Accessor
first(): returns the element at the front without removing it
size(): returns the number of elements in the queue
isEmpty(): returns a boolean indicating whether the queue is empty

Boundary Cases

Attempting dequeue() or first() on an empty dequeue returns null

Stacks

Update: Full iff t == S.length(Capacity); typo fixed in slides!

Definitions

A collection of objects that are inserted and removed according to the LIFO(Last In, First Out) rule, that is, both insertions(push) and deletions(pop) are at the top of the stack.

Keep-Track Constants

t: keeps track of the index of the top element(size = t+1)

Modifiers

push(e): add elements e to the top of the stack
pop(): removes and returns the top element from the stack, of null if the stack is empty

Accessors

top(): returns the top element of the stack or null isf the stack is empty, and do not remove it
size(): returns the number of elements in the stack
isEmpty(): returns a boolean indicating whether the stack is empty