LinkedList

Question 1

Is a Linked List Random or Sequential Access?

Answer 1

Sequential

Question 2

Is a LinkedList a linear data structure?

Answer 2

Yes

Question 3

Each element is created as a separate…

Answer 3

Object, referred to as a Node

Question 4

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

Answer 4

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

Question 5

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

Answer 5

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

Question 6

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

Answer 6

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

Question 7

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

Answer 7

The HEAD Node.

Question 8

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

Answer 8

The TAIL Node.

Question 9

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

Answer 9

HEAD, MIDDLE, TAIL.

Question 10

How do we ADD a Node to the Head of LinkedList?

Answer 10

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.

Question 11

How do we DELETE a Node from the Head of LinkedList?

Answer 11

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

Question 12

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

Answer 12

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.

Question 13

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

Answer 13

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

Question 14

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

Answer 14

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

Question 15

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

Answer 15

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

Question 16

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

Answer 16

O(n). Must do Linear Search.

Question 17

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

Answer 17

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

Question 18

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

Answer 18

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

Question 19

Examples of uses for LinkedLists?

Answer 19

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.

Question 20

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

Answer 20

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.

Question 21

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

Answer 21

Node { value, next }

List { length, head, tail }

Question 22

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

Answer 22

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.

Question 23

What are the advantages of Linked List over an array?

Answer 23

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.

Question 24

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

Answer 24

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.