DSA - Arrays, Linked Lists & ADTs

Question 1

Define an Array

Answer 1

Data Structure stored as contiguous list of cells OR sequences of bytes in memory.

Question 2

What does INDEXING mean?

Answer 2

Giving each element in the array a value, first cell with have index 0 and final cell will have index ((length of array) -1 ).

Question 3

What is a TYPE?

Answer 3

Type refers to the DATA TYPE of the Data Structure.

OR

A set of Possible values (ADTs)

Question 4

What is the time access any element in the array?

Answer 4

Constant Time regardless of the index

Question 5

Code to create ARRAY

Answer 5

int[ ] nums = new int [4]

Question 6

IN int[ ] nums = new int [4] what is nums?

Answer 6

The array name OR identifier

Question 7

IN int[ ] nums = new int [4] what does int[] do?

Answer 7

Declares the datatype of Arrays

Question 8

IN int[ ] nums = new int [4] what does new do?

Answer 8

Allocates memory for the Array

Question 9

IN int[ ] nums = new int [4] what does 4 represent?

Answer 9

Declares how many elements are in our Array

Question 10

How to get values from Array?

Answer 10

DT val = nums[0],
where DT = Datatype

Question 11

In Datatype val = nums[0] what does DT val represent?

Answer 11

Initialises the variable value and assigns the datatype

Question 12

In Datatype val = nums[0] what does num[0]?

Answer 12

nums[0] declares the array and which index value we want

Question 13

How to Assign Values in Arrays?

Answer 13

nums[i] = 23 , where i is an index in the Array

Question 14

How to find Length of the Array?

Answer 14

len = length(nums)

Question 15

Why is it important to use length of the Array?

Answer 15

Important when using if statements OR loops to find values in the Arrays or add items to an array.

Question 16

How much memory does an integer occupy?

Answer 16

4 bytes

Question 17

How do you calculate OFFSETS?

Answer 17

Index of Element * NO. bytes for Data type

Question 18

List ADTs using ARRAYS

Answer 18

List ADTs and arrays are more sophisticated than Arrays, however tend to use basic Arrays when implementing them;

ADTs lists have more complex operations i.e- list size, sort list, concatenating list, etc.

Question 19

Memory Management using Java:

Answer 19

• Memory allocation is automatic
• Freeing memory is automatic (Using garbage collector)
• Bounds of arrays are checked (Check if array is out of range)
• Slow & Safe

Question 20

Memory Management using C/C++

&

What does Explicit mean

Answer 20

1- Allocation are explicit
2- Freeing memory is explicit
3- Bounds are not checked

• Fast & Dangerous

Explicit 1) Need to allocate space & include Data Type
2) Must free up allocated space otherwise causes error and Data will never get removed.

Question 21

Common Mistakes in Array

Answer 21

int[ ] nums = new int [4]
int[4] is an error
The list has no index 4, the range of the index is 0-3

Java will return an error but in C/C++ will lead to corruption of data in memory

Question 22

Define What a Linked List is:

Answer 22

• Data structure in which the objects are ordered linearly
• Order determined by the pointer in each object (NODE)
• Collection of NODES connected to each other

Question 23

What is a Singly Linked List ?

Answer 23

Each element has a next pointer NO prev pointer
(CAN ONLY POINT TO NEXT NODE)

Question 24

What is Doubly Linked List?

Answer 24

Can point to prev node as well as next node
(CAN BE CIRCULAR OR NOT DEPENDS IF FIRST NODE POINTS TO LAST)

Question 25

What is a Sorted Linked List?

Answer 25

Linear order of list corresponds to linear order of key stored in elements of list

Question 26

What is Not Sorted Linked List?

Answer 26

Elements appear in Any order

Question 27

What is a Circular Linked List?

Answer 27

All nodes can point to prev & next node, First points to last node for prev node and last points to First node for next pointer

Question 28

What is a Non Circular Linked List?

Answer 28

Can Be anything else but a circular Linked List

Question 29

What is a pointer?

Answer 29

Points to the next node, Stores the address of the following block

Question 30

What is the END pointer?

Answer 30

- Indicates end of list - NULL can be used to represent END (Can also be -1/0) - It is an invalid reference therefore cannot be used to continue list

Question 31

What does List Variable do?

Answer 31

Contains a head pointer that holds the address pointing to first node.

Question 32

Does Linked List need to be Stored in Order in Memory?

Answer 32

NO

Question 33

Is Linked List Fixed?

Answer 33

No, so you can insert and delete items you want

Question 34

Difference in Array and Linked List to find specific position ?

Answer 34

Array uses index to get to a position. Linked List requires you to traverse through entire list to get to that position.

Question 35

How to Search through Linked List?

Answer 35

To Find an element: - Traverse it by checking value in each cell and continue checking by using pointer to check next nodes. - Continue traversal till you find the item or reach end pointer

Question 36

WORST Time Complexity of Linked List:

Answer 36

O(n) --> due to searching entire list & list length is = n

Question 37

Define Constant

Answer 37

No. of Operations does not depend on No. of elements

Question 38

Define Linear

Answer 38

Increase the number of elements by factor n, then operations cost will also increase by a factor n (WORST CASE)

Question 39

What does the command/code a.val do?

Answer 39

Outputs the value of the Node it is on

Question 40

What does the command/ code a.next do?

Answer 40

Points to the next node from the node a

Question 41

What does the command/code a.prev do?

Answer 41

Points to the prevoius node from node a - Doubly Linked List ONLY

Question 42

What does the command/ code a.next.val do?

Answer 42

Outputs the value on the next node from node its on

Question 43

Define ADTs :

Answer 43

Man Made/ Programmer developed Data Type implemented for a specific reason -LIST is an ADTs

Question 44

How do you specify a List in JAVA

Answer 44

List --> list of INTS List --> List of Strings List = new ArrayList(); --> creates a list with a variable length List = new LinkedList(); --> creates a list with a variable length

Question 45

How to Write an Array based List?

Answer 45

ArrayList

Question 46

How to Write an Linked List based List?

Answer 46

LinkedList

Question 47

What are ADTs

Answer 47

Types with associated operation, whose representations is hidden to the user. All the other operations of ADT user needs to be specified

Question 48

Is the List type int if a list of integers contain the type int?

Answer 48

No it is a CONTAINER TYPE which is more complex

Question 49

What is Recursive Algorithm?

Answer 49

- A function/method that calls itself -less code --> less Internal memory - More RAM space required - Runs till meets or Completes BaseCase -Faster / Easier to code

Question 50

CODE for Inserting into a ARRAY by SHIFTING UP:

Answer 50

maxsize = 100 Point [] locations = new Point [maxsize]; int size = 0; VOID insert (int pos, POINT pt){ if (size == maxsize ){ throw new ARRAYFULLEXCEPTION("Location_array") } for (int i = size -1; i >= pos ; i-- ){ // copy entry in pos i one pos towards the end locations[i+1] = locations[i]; } locations[pos] = pt; size++; }

Question 51

What is a Durable Array?

Answer 51

It: -Provides Maxsize -Gives illusion that you are changing size -Make sure you don't go over Maxsize

Question 52

CODE to DELETE Beginning of Linked List

Answer 52

if list = END then ERROR("Cannot Remove a node from empty-list") else list= list.next;

Question 53

CODE to DELETE End of Linked List

Answer 53

if list = END then ERROR("Cannot Remove a node from empty-list") else if list.next == END then list = END; else while cursor.next.next != END do cursor = cursor.next; end cursor.next = END;

Question 54

How to Create a Node in Linked List?

Answer 54

Class Node{ int val; Node next; } Node list = END;

Question 55

CODE to insert at Beginning of the List:

Answer 55

void insert_beg(Node list, int number){ newNode = new Node(); newNode.val = number; newNode.next = list; list = newNode; }

Question 56

CODE FOR LOOKUP :

Answer 56

int value_at (Node list, int index){ int i = 0; Node nextnode = list; while (true){ if (nextnode == END){ throw new OutOfBoundException(); } if (i== index){ break; } nextnode = nextnode.next; i++; } return nextnode.val; }

Question 57

What is CODE for is_empty() | LL

Answer 57

Boolean is_empty(NODE list) { return (list == END); }

Question 58

CODE Insert at END of Linked List

Answer 58

void insert_end(NODE list, int number) { newblock = new Node(); newblock.val = number; newblock.next = END; if (list == END) { list == newblock; } else { cursor = list; while (cursor.next != END) { cursor = cursor.next; } cursor.next = newblock; } }

Question 59

CODE Insert at Beginning of Linked List

Answer 59

void insert_beg (NODE list, int number ){ newNode = new Node(); newNode.val = number; newNode.next = list; list = newNode;

Question 60

What does the First Block in a Linked List hold?

Answer 60

Stores a number/ the data

Question 61

What does the second Block in a Linked List hold?

Answer 61

Stores the address of the following block

Question 62

What does List operation Last Element do?

Answer 62

- First Check if entire list is empty, if it is return Error - If not Empty Check if rest of list except first element is empty return first element, -Otherwise Recursively go through the rest of the list bare first element to find the last non-empty value

Question 63

What is the CODE for List operation Last Element?

Answer 63

last(lst) { if( isEmpty(lst)) error("Error: _empty_list_in_last") else if (isEmpty(rest(lst))) return first(lst) else return last(rest(lst)) }

Question 64

What does the Constructor EmptyList do?

Answer 64

Returns an empty List

Question 65

What does the Constructor MakeList(element, list) do?

Answer 65

Adds an element at the front of a list

Question 66

What does the Accessor first(list) do?

Answer 66

Returns the first element of the list

Question 67

What does the Accessor rest(list) do?

Answer 67

Returns the all elements of list bare First

Question 68

What does the Accessor isEmpty(list) do?

Answer 68

Reports whether a list is empty

Question 69

What is the CODE for List operation getElementByIndex?

Answer 69

getElementByIndex(index, lst) { if( index <0 or isEmpty(lst)) error("Error:_index_out_of_range") elseif (index == 0) return first(lst) else return getElementByIndex (index -1, rest(lst)) }

Question 70

What is the CODE for List operation append?

Answer 70

append (lst1,lst2){ if(isEmpty(lst1)) return lst2 else return MakeList(first(list1), append(rest(lst1), lst2) }

Question 71

What does the List operation append?

Answer 71

Joins or combines 2 lists together - Adds first element on from lst1, then rest of lst1 till it is empty and then lst2 till it is empty - which creates a new list