Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

CS YEAR ONE > DSA - Arrays, Linked Lists & ADTs > Flashcards

DSA - Arrays, Linked Lists & ADTs Flashcards

1
Q

Define an Array

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

What does INDEXING mean?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

What is a TYPE?

A

Type refers to the DATA TYPE of the Data Structure.

OR

A set of Possible values (ADTs)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

What is the time access any element in the array?

A

Constant Time regardless of the index

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Code to create ARRAY

A

int[ ] nums = new int [4]

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

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

A

The array name OR identifier

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

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

A

Declares the datatype of Arrays

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

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

A

Allocates memory for the Array

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

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

A

Declares how many elements are in our Array

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

How to get values from Array?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

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

A

Initialises the variable value and assigns the datatype

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

How to Assign Values in Arrays?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

How to find Length of the Array?

A

len = length(nums)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Why is it important to use length of the Array?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

How much memory does an integer occupy?

A

4 bytes

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

How do you calculate OFFSETS?

A

Index of Element * NO. bytes for Data type

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

List ADTs using ARRAYS

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

Memory Management using Java:

A
  • 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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

Memory Management using C/C++

&

What does Explicit mean

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

Common Mistakes in Array

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

Define What a Linked List is:

A
  • 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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

What is a Singly Linked List ?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

What is Doubly Linked List?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Q

What is a Sorted Linked List?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
26
Q

What is Not Sorted Linked List?

A

Elements appear in Any order

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
27
Q

What is a Circular Linked List?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
28
Q

What is a Non Circular Linked List?

A

Can Be anything else but a circular Linked List

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
29
Q

What is a pointer?

A

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

30
Q

What is the END pointer?

A
  • 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
31
Q

What does List Variable do?

A

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

32
Q

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

A

NO

33
Q

Is Linked List Fixed?

A

No, so you can insert and delete items you want

34
Q

Difference in Array and Linked List to find specific position ?

A

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

35
Q

How to Search through Linked List?

A

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

36
Q

WORST Time Complexity of Linked List:

A

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

37
Q

Define Constant

A

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

38
Q

Define Linear

A

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

39
Q

What does the command/code a.val do?

A

Outputs the value of the Node it is on

40
Q

What does the command/ code a.next do?

A

Points to the next node from the node a

41
Q

What does the command/code a.prev do?

A

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

42
Q

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

A

Outputs the value on the next node from node its on

43
Q

Define ADTs :

A

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

44
Q

How do you specify a List in JAVA

A

List <int> --> list of INTS
List<String> --> List of Strings</String></int>

List<DATATYPE> = new ArrayList<DATATYPE>(); --> creates a list with a variable length</DATATYPE></DATATYPE>

List<DATATYPE> = new LinkedList<DATATYPE>(); --> creates a list with a variable length</DATATYPE></DATATYPE>

45
Q

How to Write an Array based List?

A

ArrayList<DATATYPE></DATATYPE>

46
Q

How to Write an Linked List based List?

A

LinkedList<DATATYPE></DATATYPE>

47
Q

What are ADTs

A

Types with associated operation, whose representations is hidden to the user.

All the other operations of ADT user needs to be specified

48
Q

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

A

No it is a CONTAINER TYPE which is more complex

49
Q

What is Recursive Algorithm?

A
  • 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
50
Q

CODE for Inserting into a ARRAY by SHIFTING UP:

A

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++;
}

51
Q

What is a Durable Array?

A

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

52
Q

CODE to DELETE Beginning of Linked List

A

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

53
Q

CODE to DELETE End of Linked List

A

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;

54
Q

How to Create a Node in Linked List?

A

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

55
Q

CODE to insert at Beginning of the List:

A

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

56
Q

CODE FOR LOOKUP :

A

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;
}

57
Q

What is CODE for is_empty()

LL

A

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

58
Q

CODE Insert at END of Linked List

A

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;
}
}

59
Q

CODE Insert at Beginning of Linked List

A

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

60
Q

What does the First Block in a Linked List hold?

A

Stores a number/ the data

61
Q

What does the second Block in a Linked List hold?

A

Stores the address of the following block

62
Q

What does List operation Last Element do?

A
  • 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
63
Q

What is the CODE for List operation Last Element?

A

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

64
Q

What does the Constructor EmptyList do?

A

Returns an empty List

65
Q

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

A

Adds an element at the front of a list

66
Q

What does the Accessor first(list) do?

A

Returns the first element of the list

67
Q

What does the Accessor rest(list) do?

A

Returns the all elements of list bare First

68
Q

What does the Accessor isEmpty(list) do?

A

Reports whether a list is empty

69
Q

What is the CODE for List operation getElementByIndex?

A

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))
}

70
Q

What is the CODE for List operation append?

A

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

71
Q

What does the List operation append?

A

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

CS YEAR ONE (15 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions