CS2040S: ADT List, stack and queue

Linked List

A linear data structure that uses pointers to point to the other nodes. Elements are not stored in contiguous memory.

Abstract Data Type

A type or class for objects whose behavior is defined by a set of values and a set of operations.

ADT and Data structures, their relationship

ADT is just a concept that implements some data structures. 

E.g Arraylist and Queues are just adt concepts that makes used of arrays or linked list.

Data structures on the other hand, are concrete memory spaces.

Linked List Vs Arrays

Based on Visual Go, we can see the way that linked list work in comparison to compact arrays:

Get:
  Arrays: O(1)
  Linked List: O(n) , Iterate the entire list to get

Search:
  Arrays: O(n), To search for value, have to iterate the entire list
  Linked List: O(n), Iterate entire

Insert:
  Arrays: O(n), Have to create a new array
  Linked List: O(n), Iterate the entire till reach the position

Remove:
  Arrays: O(n), Have to create a new arrays
  Linked List: O(n), Have to iterate the entire linked list

Remove Node:
Array: No nodes
Linked List: O(1)
//We don't need to know the index

Detecting palindrome using a linked list will fastest up to n time


1. Compare each first letter with the last one
-> n*n
O(n^2)


2. Use array as an buffer:
-> Iterate the list (n)
-> Using index, iterate twice (2n)
-> 2n +  n = 3n (n)
O(n) but cost S(n)

Using Recursion to solve palindromes.

e.g (Head)L->U->K->E

1. Imagine that there is a function that is already swap the last few letters

we will get:

E->K->U<-L(head)->U

2. After swapping, we realised that there are problems

- U is pointing wrong

- Head is still at L

3. We can change by doing Head.next.next = head

this will give us

E->K->U->L(Head)->U

4. We then do Head.next = null

To set L to not point anything

E->K->U->L(head)

5. Finally we make sure that E is head

head = temp;

(Head) E->K->U->L

Palindromes: What if we Adapt the data structure into a doubly link list?

Will it save space?

It depends

We don't know if the pointer will use up memory space.

Palindromes: Using stacks

1. Get midpoint of an list, O(n)

2. Run through first half of linked list and push each element on stack O(n/2) => O(n)

3. Iterate the remaining half and check each of the pop element of the stack O(n)

O(n) and S(n/2)

Palindromes: Reversing the second half

1. Get midpoint of an list O(n)

2. Reverse the second half O(n)

3. Iterate and compare

O(n) and S(1)

Best time strategy

1. Easiest way to solve the problem

2. Focus on correctness then efficiency

3. Ask

- What operations are needed

- What data structures do these operation work well

- Is data random or sorted

4. Improve

- how to make faster?

- Assumptions made

- Divide and conquer?

Implement queue using other ADT

Array:

Enqueue(x): O(1)

We just insert to the last pointer

Peek(): O(1)

We just access the first variable

Dequeue(): O(n)

We need to remove and shift all the variables up by one index

Issues: Fixed sized

Singly Linked List

Enqueue(x): O(1)

Create a new node and put it at the back, no need to iterate

Peek(): O(1)

Check the first object

Dequeue(): O(1)

Remove the first object, other variables automatically become new head

Issues: Variable sized

We should use Linked List to implement our Queue adt

Dynamic arrays

Arrays that can grow, but in actual fact, we are just increasing the size of the array by generating a new array every time the end is reached.

Using other ADT to implement stacks

Dynamic Array

Push: O(1) (Amortized)

Peek: O(1)

Pop: O(1)

Push to the back

Singly Linked List

Push: O(1) 

Peek: O(1)

Pop: O(1)

Push to the front

We can use both methods to implement the stack

Can we implement a queue using stacks?

Yes, use two stacks

Enqueue: Add to the top of stack A

Dequeue:
Pop all elem from stack a to be

Remove the last element

pop of all element from stack B to stack A (Not needed, just alternate)

Computational Cost

Constant time for enqueue

2n Operations for dequeue

<Prev                        Next>