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

Question 4

What is each individual element called?

Answer 4

Node

Question 5

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

Answer 5

1. The data (could be complex objects)

2. The reference (or pointer) the the next Node in the List.

Question 6

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

Answer 6

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

Question 7

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

Answer 7

The reference to the next Node will be null.

Question 8

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

Answer 8

The HEAD Node.

Question 9

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

Answer 9

The TAIL Node.

Question 10

Data can flow in and out of …. point of a LinkedList.

Answer 10

Any

Question 11

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

Answer 11

HEAD, MIDDLE, TAIL.

Question 12

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

Answer 12

We make the new head Node point to the old head Node and update what Node we consider to be the head node in our implementation.

Question 13

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

Answer 13

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

Question 14

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

Answer 14

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 15

How do we REMOVE a Node somewhere in the middle of a LinkedList? (1 step)

Answer 15

Make the pointer of the Node previous to the one we’re removing, to now point to the Node after the one we’re removing.

Question 16

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

Answer 16

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

Question 17

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

Answer 17

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

Question 18

What is a pirate themed analogy of a LinkedList?

Answer 18

It’s like a treasure map. You follow the directions to one place and then it tells you the where to go to find the next place and so forth.

Question 19

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

Answer 19

O(n). Must do Linear Search.

Question 20

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

Answer 20

1. If inserting at the head of the list then O(1)

2. Anywhere else then it’s O(n)

Question 21

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

Answer 21

1. If deleting at head of the list then O(1)

2. Anywhere else then it’s O(n)

Question 22

Examples of uses for LinkedLists?

Answer 22

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

Question 23

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

Answer 23

The pointers/references only point to the next Node in the list. You can’t navigate back towards the head node. With a Doubly-LinkedList you can traverse the list in either direction.