1
Q

Is a Linked List Random or Sequential Access?

A

Sequential

2
Q

Is a LinkedList a linear data structure?

A

Yes

3
Q

Each element is created as a separate…

A

Object, referred to as a Node

4
Q

A Node is made up of two parts. What are they?

A
1. The data (could be complex objects)
2. The reference (or pointer) the the next Node in the List.
5
Q

What is a real-world analogy for a ACCESSING an element in a LinkedList?

A

A tape measure. To get to inch 72 you first have to traverse inches 1 through 71.

6
Q

How do we know when we have reached the end of a LinkedList?

A

The reference to the next Node will be null.
(Or a sentinel Node)

7
Q

What is the term for the first Node in a LinkedList?

A

8
Q

What is the term for the last Node in a LinkedList?

A

The TAIL Node.

9
Q

What are the three places in a LinkedList that we can ADD or REMOVE data?

A

10
Q

A

1) Create a Node, from the given value
2) make the new head Node point to the old head Node
3) update what Node we consider to be the head Node.

11
Q

A

We make the 2nd Node in the list our new head Node and make the old head Node point to null.

12
Q

How do we ADD a Node somewhere in the middle of a LinkedList? (2 steps)

A
1. Make the pointer of the new Node point to the Node after the location we want to insert at.
2. Set the Node before the location we want to insert at to point towards the new Node.
13
Q

How do we REMOVE a Node somewhere in the middle of a LinkedList?

A

1) Make the pointer of the Node previous to the one we’re removing, to point to the Node after the one we’re removing.
2) Make the removed node point to null

14
Q

How do we REMOVE a Node at the tail of a LinkedList?

A

Set the previous tail to point to a null value instead of the current tail.

15
Q

What is the BigO of ACCESSING an element in a LinkedList?

A

O(n). Sequential data structure, worst-case you have to go via every element in the list.

16
Q

What is the BigO of SEARCHING for an element in a LinkedList?

A

O(n). Must do Linear Search.

17
Q

What is the BigO of INSERTING an element in a LinkedList? (2 depending on location)

A
1. If inserting at the head of the list then O(1)
2. Anywhere else then it’s O(n)
18
Q

What is the BigO of DELETING an element in a LinkedList? (2 depending on location)

A
1. If deleting at head of the list then O(1)
2. Anywhere else then it’s O(n)
19
Q

A

Music playlists. The track info is the data and it points to the next song in the playlist.
PhotoViewing app, the ‘next’ button links to the next image in the list.
As the ‘backing’ data structure for other data structures like Queues and Stacks.

A Pirate’s treasure map.

20
Q

What is a Singly-LinkedList? What is its main drawback?
And what data structures gets around this drawback?

A

The pointers/references only point to the next Node in the list.
You can’t navigate back towards the head node.

Doubly-LinkedList/deque you can traverse the list in either direction.
ArrayDeque you can use the index to traverse.

21
Q

Describe the Node class and the Linked List class for a Singularly linked list

A

Node { value, next }

List { length, head, tail }

22
Q

Are linked lists considered linear or non-linear data structures?

A

On the basis of data storage, it is considered as a non-linear data structure.

On the basis of the access strategy, it is considered as a linear data-structure.

23
Q

A

The size of a linked list can be incremented at runtime which is impossible for the array.

The List is not required to be contiguously present in the main memory. Nodes can be stored anywhere in memory connected through the links.

The List is dynamically stored in the main memory and grows as per the program demand. While the array is statically stored in the main memory, size of which must be declared at compile time.

The number of elements in the linked list are limited to the available memory space while the number of elements in the array is limited to the size of an array.

24
Q

How do you find the middle node in a linked list?

A

Use two pointers, one goes fast [2 steps] the other goes slow [1 step], when the fast node hits the end of the list the slow node will be at 1/2.