LinkedLists

Question 1

What are the main limitations of an ArrayList that may provoke using a LinkedList?

Answer 1

1. There’s a fixed number of elements in the underlying array - Although the ArrayList class provides functionality to grow the underlying array, it can be time consuming and thus introduce latency.
2. You cannot easily insert an element in between others - When this is done all of the other elements in the ArrayList are shifted so you lose track of the original position.
3. Searching for a value can be very slow

Question 2

What is a LinkedList?

Answer 2

A data structure that stores elements in arbitrary, noncontiguous memory locations to facilitate efficient insertion and removal, but also provides additional information to link the elements together. The element plus the link is referred to as a node. The first node in the list is referred to as the head and the last node in the list is known as the tail. Note that the tail links to “null”.

Question 3

What is the Node class?

Answer 3

A LinkedList stores elements in a sequence of nodes, which are represented by the Node class. Because the methods of the LinkedList class and the Iterator class have frequent access to the Node instance variables, we do not make the instance variables of the Node class private. Instead, we make Node a private inner class of the LinkedList class. The class definition is as follows:

public class LinkedList<e> {<br></br> class Node {</e>

//The data stored in the node

E value;

//Node object that is a link to the next node in the list

Node next;

//This is the constructor

Node(E value) {

this.value = value;

}

}

//References to the first and last nodes in the list

protected Node head = null;

protected Node tail = null;

}

Question 4

How do you add an element to the beginning of a LinkedList?

Answer 4

You need to do three things: First, create the new node. Next, set it’s link to the node that will come after it, which in this case is the head. Finally, update the head of the LinkedList. You just need to make sure you handle the situation in which the list was previously empty so this new node is the head and the tail. This additional code is circled below:

Question 5

How do you add a new element to the end of a LinkedList?

Answer 5

Similar to adding a new node to the beginning of the LinkedList, there are three steps to doing this. First, you create the new node. Then you set the next node of the tail to refer to the new one. Finally, you update the tail to refer to the new node. You similarly just need to handle situations in which the list was empty and the new node is the head and tail! This is outlined below:

Question 6

How do you add an element somewhere in the middle of a LinkedList?

Answer 6

You need to traverse, or iterate through, all elements in the list until you reach the point at which you want to insert the new node. Then you need to update the links of the nodes before and after the new one. There are quite a few exceptions that have to be handled in this case. They are demonstrated below:

Question 7

How do you remove the first element from a LinkedList?

Answer 7

You simply update the head to refer to the second node in the LinkedList. It is not actually removed, but unlinked and eventually it is garbage collected. The code is as follows:

Question 8

How do you remove the last element from a LinkedList?

Answer 8

You need to do two things. First, you need to update the link of the second to last element so that it points to null. Then update the tail to point to that second to last node. Since we don’t have a direct link to the second to last node, we need to walk through the links in the list until we find it.

Question 9

How do you remove an element from the middle of a LinkedList?

Answer 9

You walk through all links in the list from the head to the one preceeding the link you want to remove. Then you update it’s link to the node after the one you want to remove so it’s skipped or removed from the list. The code for this is shown below:

Question 10

How can you get an element from a LinkedList using its index?

Answer 10

You use the get( ) method. The code for this is shows below. Note that as we’ve seen before, you cannot directly access an element in a LinkedList by its index. You need to start at the head and advance n nodes until you reach the one you want to retrieve. The code for this is shown below:

Question 11

How can you determine if a value is contained in a LinkedList?

Answer 11

You can use the contains( ) method. The code for this is shown below. Note that as with ArrayLists, you cannot instantly determine if a value is contained in a LinkedList because you can only 1 value in the list with the target value at a time so you need to inspect each value starting with the head until we find what the target value.

Question 12

For a linked list that contains 3 or more elements, if head is a reference to the first node of a LinkedList, what happens when you run the operation head = tail; ?

Answer 12

It removes all nodes from the LinkedList except for the last element.

Question 13

For what operation is a LinkedList slower than an ArrayList?

Answer 13

Retrieving an element by its index.

Question 14

Answer 14

• A drive through ordering system
• A waitlist for standby passengers at an airport
• A CPU that is shared among different jobs based upon arrival time

Question 15

What is a Stack?

Answer 15

An abstract data type that is a specialized version of LinkedList and works like a LinkedList, but only has two operations that allow you to add and remove elements to the head, or top. They are:

• push( ) - adds an element to the head / top
• pop( ) - removes an element from the head / top

As this illustrates, Stacks are therefore a LIFO (last in, first out) data structure. They are also one of the simplest of all data structures, yet among the most important as they are used in a host of different applications and in more complex algorithms.

Question 16

What is an abstract data type (ADT)?

Answer 16

An abstract data type (ADT) is a model of a data structure that specifies:

• the characteristics of the collection of data
• the operations that can be performed on the collection

It’s abstract because it doesn’t specify how the ADT will be implemented. In Java, we implement these with an interface that specifies the methods but does not define them. Given that an interface serves as a type definition, but cannot be directly instantiated, we must provide one or more concrete classes that implement the ADT.

Question 17

What are a few common implementations of a Stack data structure?

Answer 17

The name “stack” is derived from the metaphor of a stack of plates in a spring-loaded, cafeteria plate dispenser. In this case, the fundamental operations involve “pushing” and “popping” the plates off of the stack. An even more amusing example is the Pez candy dispenser, which is a physical implementation of a stack.

In software engineering, there are two common implementations of a stack data structure:

• Internet Web Browsers - these store the address of recently visited sites on a stack. Each time a user visits a new site it is “pushed” onto the stack of addresses. The browser then allows the user to “pop” back to the previously visited sites using the “back” button.
• Text Editors - these provide an “undo” mechanism that cancels recent operations and reverts back to a former state of a document. These undo operations can be accomplished by keeping text changes in a stack.

Question 18

How is a Stack implemented in the Java collections framework?

Answer 18

Question 19

What is a Queue?

Answer 19

A data structure that is a specialized version of a LinkedList and works like a LinkedList, but only has two operations:

• add( ) - adds an element to the rear / tail
• remove( ) - removes an element from the front / head

Note that a Queue is a FIFO (first in, first out) data structure.

Question 20

What are a few common implementations of the Queue ADT?

Answer 20

A queue is a logical choice for a data structure to handle calls to a customer service center or managing a waiting list at a restaurant. They’re also used by computing devices such as networked printers and web servers that respond to requests.

Question 21

How is a Queue implemented in the Java collections framework?

Answer 21

This data structure is implemented as an interface, not a Class, and therefore cannot be instantiated. Therefore, when a Queue is declared it is done as type Queue but instantiated as a LinkedList (this is possible because the LinkedList class implements the Queue interface). For example:
*protected Queue<integer> ticketRequests = new LinkedList<interger>( );</interger></integer>*

Question 22

How can you determine if a Stack or Queue is empty?

Answer 22

• empty( ) - tests if a Stack is empty
• isEmpty( ) - tests if a Queue is empty

Question 23

How do you remove and return the node at the head of a Stack and a Queue?

Answer 23

• Stack.pop( )
• Queue.remove( )

Question 24

How do you return the node at the head of a Stack or Queue without removing it?

Answer 24

• Stack.peek( )
• Queue.peek( )

Question 25

To which end of the LinkedList does **Stack.push(E element)** insert a new node?

Answer 25

The head

Question 26

To which end of the LinkedList does **Queue.add(E element)** insert a new node?

Answer 26

The tail

Question 27

How is the LinkedList collection implemented in the Java API?

Answer 27

* **LinkedList( )** - constructs an empty LinkedList * **LinkedList(Collection extends E\> c)** - constructs a new LinkedList containing the elements of the specified collection in the order that they are returned by the collection's iterator * **add(E element)** - adds an element to the end (tail); this works the same way as addLast * **add(int index, E element)** - adds an element to the specified index position * **addFirst(E element)** - adds an element to the front (head) * **addLast(E element)** - adds an element to the end (tail) * **set(int index, E element)** - replaces an element at a specified index position with the specified value * **remove( )** - removes and returns the first element (head); works the same way as removeFirst * **removeLast( )** - removes and returns the last element (tail) * **remove(int index)** - removes and returns an element at a specific index location * **contains(E element)** - indicates if the list contains a specific value * **get(int index)** - returns the element at a specific index location * **getFirst( )** - returns the first element in the list (at the head) * **getLast( )** - return the last element in the list (at the tail)

Question 28

What is a "singly" LinkedList versus a "doubly" LinkedList?

Answer 28

In a singly LinkedList each Node has a link to the next Node, whereas in a doubly LinkedList each Node has a link to the previous and next Nodes. This allows the list to be traversed in reverse order, starting from the tail, as opposed to starting at the beginning at the head.

Question 29

How is a doubly LinkedList implemented in Java?

Answer 29

To implement a doubly LinkedList in Java, you just make one simple change to the structure of a LinkedList: add a field for the previous Node to the class definition. This is shown below:

Question 30

How do you traverse a doubly LinkedList from the end, or tail?

Answer 30

You initialize the iterator, in this case the current Node, to the tail and iterate through the list by updating the current Node to the previous Node. This is illustrated in the code below:

Question 31

How do you add an element to the beginning / head or the end / tail of a doubly LinkedList?

Answer 31

This works the same way as it does for singly LinkedLists except that you need to update the previous Node as well. Therefore, this just requires one additional line of code in the addFirst and addLast methods, as shown below (note that this example assumes the head and tail are not null):

Question 32

How do you add an element somewhere in the middle of a doubly LinkedList?

Answer 32

This works the same way as it does for singly LinkedLists except that you need to update the previous Nodes as well. Therefore, this just requires two additional lines of code in the addFirst and addLast methods, as shown below (note that this example assumes the head and tail are not null):

Question 33

When removing a node at a specified index in the middle of a doubly LinkedList containing at least 3 nodes, which steps are necessary to complete this task?

Answer 33

current. prev.next = current.next; current. next.prev = current.prev;

Question 34

How do you reverse a singly LinkedList?

Answer 34

To do this you need to create three variables for the current, next, and previous Nodes in the list and iterate through the Nodes incrementally updating them: public void reverse() { Node previous = null; Node current = head; Node next = null; while(current != null) { next = current.next; current.next = previous; previous = current; current = next; } tail = head; head = previous; }