Practical Session #4 - ADTs: Array, Queue, Stack,Linked List

Basic Data Structures and Abstract Data Types
ADT / Abstract Data Type
A collection of data-storing entities with operations to create, access, change, etc.
Array / A linear sequence of elements that supports access to its elements by their indexes. Supports the following basic methods:
  • elementAt(i) – returns the element at index i
  • insertAt(i, element) – insert new element at index i
  • removeAt(i) – remove the element in index i
  • size() – returns the size of the array

Queue / FIFO - First In First Out
ADT that supports the following operations:
  • Enqueue - insert new element at the tail of the queue
  • Dequeue - remove element from the head of the queue
  • isEmpty - returns true if the queue is empty

Stack / LIFO - Last In First Out
ADT that supports the following operations:
  • Push - add element to the head of the stack
  • Pop - remove element from the head of the stack
  • isEmpty - returns true if the stack is empty

Linked List / A data structure with linear access to the elements in it.
Each element has a pointer to the next element in the list
Doubly-Linked List / A data structure with linear access to the elements in it.
Each element has 2 pointers, one to the next element in the list and the other to the previous element
  • Important! – ADT’s can be implemented in a variety of possibilities. Below we describe ADT’s and demonstrate their implementations.

Question 1

S is a set of at most n elements, where n is given.
Each element has a unique key in the range [0...n-1]. (i.e. no 2 different elements have the same key)
Find a data structure of size O(n), that supports the following operations in the given times:

Operation / Time
Init(n) / Initialize S (S is an empty set at the beginning) / O(n)
isElement(k) / Check if S has an element whose key equals to k / O(1)
Insert(x) / Add element x to S / O(1)
Remove(k) / Remove element whose key equals to k / O(1)
isEmpty() / Check if S is empty / O(1)
hasAll / Check if S contains all the elements whose keys are
in the range [0...n-1] / O(1)

Solution: (Direct Addressing) :

  1. Array A[1..n] of pointers to elements.
    if A[k] == null, the element whose key is k is not in S.
  2. count = number of elements in S

Init (n)

for (i=0 ; i<n ; i++)

A[i] = null;

count = 0;

isElement (k)

return (A[k] != null);

Insert (x)

If(!isElement (x.key){

A[x.key] = x;

count++;

}

Remove (k)

If(isElement (k){

A[k] = null;

count--;

}

isEmpty ()

return (count == 0);

hasAll ()

return (count == n);

Question 2

Suggest 2 ways to implement a Queue using 2 Stacks.

Solution:

The queue/stack is abstract, meaning the implementation isn't known, only the interface.
In order to implement a queue we need to implement the following methods:

Enqueue(x) ,Dequeue() ,isEmpty()

We will use stack A in order to hold the queue's elements and stack B as a temporary stack. We will use the Stack ADT operations: Push(x), Pop() and isEmpty().

Enqueue (x) {

moveElements(A,B)

A.Push(x)

moveElements(B,A)

}

Dequeue ( ) {

element = A.Pop()

return element

}

isEmpty ( ) {

return A.isEmpty()

}

moveElements(X,Y) {

while (! X.isEmpty()){

temp = X.Pop()

Y.Push(temp)

}

}

Another way to implement a queue using 2 stacks:

Enqueue (x) {

moveElements(A,B)

A.Push(x)

}

Dequeue ( ) {

moveElements(B,A)

element = A.Pop()

return element

}

isEmpty ( ) {

return ( A.isEmpty() & B.isEmpty(

Question 3:

L1 and L2 are two linked lists which have a common part of size k.

The length of L1, L2 until the 1st common node is n,m respectively.

Suggest a way to find the 1st common node in O(n+m+k) time.

(k,n,m are variables, not given)

Solution :
  1. find the length of L1 and L2
  2. In the longer list, skip (L1.length-L2.legth)nodes.
  3. Traverse both lists step by step together. In the shorter list start from the first node. In the longer list start from the node you found in 2. Stop when the “next” pointer of both lists points to the same node.

time complexity:

finding the length of L1: O(n+k)

finding the length of L2: O(m+k)

finding the common link: O(m+n)

total: O(n+m+k)

Question 4:

L is a singly linked list. Starting from the first element, suggest a way to traverse forward and backward from one element to its next or previous elementat O(1). You can use only O(1) extra memory.

Solution:

Converting the list to a doubly-linked list can do the trick, but it is not allowed (will cost O(n) extra memory).

We will use two pointers:

  • current – the current link we want to traverse from.
  • prev – the previous link in the traversal.

As we traverse forward, all the links before current will be linked backward.

As we traverse backward, all the links after current will be linked forward as usual.

init()

current=head

prev=null

moveForward()

temp = prev

prev=current

curent=current.next

prev.next=temp

moveBackward()

temp=current

current=prev

prev=prev.next

current.next=temp

Question 5:

A is a Boolean (1 or 0 values) matrix of size n*n.

Find a data structure that supports the following operations in the given time:

Operation / Time
init(n) / Initialize A with the value 1 / O(n2)
flip(i,j) / A[i,j]=!A[i,j] / O(1)
hasRowOf1 / Return true iff A has a row that contains only 1-s / O(1)
hasRowOf0 / Return true iff A has a row that contains only 0-s / O(1)

Solution:

We will use the following data structures:

  • A[n][n] – the matrix
  • Sum[n] – An array containing sums of the rows in A. Sum[i] = the sum of the row i in A.
  • count1 = how many cells in Sum contain n
  • count0 = how many cells in Sum contain 0

init()

fill A with 1’s

fill Sum with n.

count1=n

count0=0

hasRowOf1()

return count1>0

hasRowOf0()

return count0>0

flip(i,j)

if (A[i][j]==0) {

if (Sum[i]=0)

count0- -

Sum[i]++

if (Sum[i]=n)

count1++

A[i][j]=1

}

else {

if (Sum[i]=n)

count1- -

Sum[i]--

if (Sum[i]=0)

count0++

A[i][j]=0

}

Question 6:

Suggest a way to implement an array of integers so that assignment of some value INIT_VAL to all cells of an array will take O(1) time.

Remember that reading A[i] or writing to A[i] takes O(1) time.

Solution:

In order to implement an initialization of an array A of size n in O(1) time, we will create a new ADT called smartArray.

The smartArray ADT uses the following data structures:

  • A - the array of values
  • top – counts the number of defined elements in A
  • INIT_VAL– the value to initiate the array with
  • C – Array of defined and undefined indexes
    C[0..top-1] –indexes of defined elements in A
  • B – array of pointers to the defined indexes in C
    B[k] = the index of k in the array C

Example:

x = new smartArray[n]

x.init(0)

x.write(2,20)

x.write(4,40)

x.write(5,50)

a = x.read(4) > the value of a is 40

b = x.read(3) > the value of b is 0

Assumptions:

  • The value of an undefined element B[i] is an unexpected non-negative number.
    Thus, for an undefined index, the comparison B[i]<top can be either true or false.
  • The and expression is evaluated from left to right.
    Thus, C[B[i]]=i is evaluated only if B[i] < top.

The smartArray ADT supports the following methods:

NewSmartArray(n)

A = new int[n]

B = new int[n]

C=new int[n]

init(val)

INIT_VAL = val

top = 0

not_defined(i)

return !((B[i] < top)

and C[B[i]] = i))

Read(i)

if (not_defined(i))
return INIT_VAL

else

return A[i]

Write(i,val)

if (not_defined(i))
C[top] = i

B[i] = top

top++
A[i] ← val

שאלה מס' 7

נגדיר "מחסנית מינימום" כמבנה נתונים התומך בפעולות הבאות:

  • Create()– אתחול מבנה הנתונים.
  • Insert(x)– הכנסת איבר xלמבנה.
  • RemoveLast()– הוצאת האיבר שהוכנס אחרון.
  • Min()– החזרת האיבר הקטן ביותר במבנה (ללא הוצאתו).
  • ChangeMin(k)– שינוי ערך האיבר הקטן ביותר במבנה ל –k.

הנחה: כל האיברים שונים זה מזה.

הציעו מימוש ל"מחסנית מינימום", כאשר סיבוכיות הזמן הנדרשת לארבע הפעולות הראשונות היא O(1), ולפעולה ChangeMinO(t), כש –t הינו מספר האיברים במבנה שהוכנסו אחרי האיבר המינימלי (הכוונה לאיבר המינימלי לפני שהפעולה ChangeMin בוצעה).

פתרון: