Linked Data Structures

Question 1

What is a Linked List?

Answer 1

A linked list consists of a single chain of nodes each connected to the next by a link.

Question 2

What is the first node in a linked list

Answer 2

The first node, or start node in a linked list is called the head node.
The entire linked list can be traversed by starting at the head node.

Question 3

Does a linked list object contain all the nodes in the linked list directly?

Answer 3

It does not. Rather, it uses the instance variable head to locate the head node of the list. Therefore, once the head node can be reached, then every other node in the list can be reached.

Question 4

How is an empty linked list indicated?

Answer 4

1. The head instance variable contains a reference to the first node in the linked list. If the list is empty, this instance variable is set to null.
2. The linked list constructor sets the head instance variable to null. This indicates that the newly created linked list is empty.

Question 5

How do you indicate the end of a linked list?

Answer 5

The last node in a linked list should have its link instance variable set to null. That way the code can test whether or not a node is the last node.

Question 6

How do you traverse a linked list?

Answer 6

If a linked list already contains nodes, it can be traversed as follows:

1. set a local variable equal to the value stored by the head node (its reference)
2. This will provide the location of the first node.
3. After accessing the first node, the accessor method for the link instance variable will provide the location of the next node.
4. Repeat this until the location of the next node is equal to null.

Question 7

What is a stack data structure?

Answer 7

A stack data structure is not necessarily a linked data structure, but can be implemented as one. A stack removes items in the reverse order of which they were inserted. (LIFO: Last in First Out)