6. Linked Structures

Feel free to use your laptop
You are strongly encourage to work with others
- When you get stuck, ask those sitting around you for help
- Get used to working together in the labs
- Peer teaching and peer learning has been empirically shown to be very effective

6.1. Linked Structure

The goal is to create a linked structure with a series of Node objects.

6.1.1. Node Class

Create a generic Node class
Download and run the NodeTest class to ensure the Node class is implemented correctly
- This test class must be added to the project’s test folder

6.1.2. Create the Linked Structure

Write a static method in the same class as the main called makeLinkedStructure that will
- Create a linked structure containing the numbers 0 – 9
  One number referenced in each node
- Return a reference to the head of the linked structure
public static Node<Integer> makeLinkedStructure() { // ... }

Verify it works as expected by adding this to the main method and running it

Node<Integer> head = makeLinkedStructure();
Node<Integer> currentNode = head;

while (currentNode != null) {
    System.out.println(currentNode.getData());
    currentNode = currentNode.getNext();
}

6.2. Manipulating the Linked Structure

Start manipulating the linked structure by adding and removing elements.

6.2.1. Adding to the Front of the Structure

Write a static method in the same class as the main called addToFront that will
- Take a reference to the head of a linked structure and an integer to add
- Create a new Node containing a reference to the integer passed to the method as an argument
- Insert the newly created Node to the front of the linked structure
- Return a reference to the new head of the linked structure
public static <T> Node<T> addToFront(Node<T> head, T toAdd) { // ... }

Verify it works as expected by adding this to the main method and running it

head = addToFront(head, 99);
currentNode = head;
while (currentNode != null) {
    System.out.println(currentNode.getData());
    currentNode = currentNode.getNext();
}

6.2.2. Removing from the Front of the Structure

Write a static method in the same class as the main called removeFromFront that will
- Take a reference to the head of a linked structure
- Remove the first Node from the structure
- Return a reference to the new head of the linked structure
public static <T> Node<T> removeFromFront(Node<T> head) { // ... }

Verify it works as expected by adding this to the main method and running it

head = removeFromFront(head) ;
currentNode = head;
while (currentNode != null) {
    System.out.println(currentNode.getData());
    currentNode = currentNode.getNext();
}

6.2.3. Adding to the Middle of the Structure

Write a static method in the same class as the main called addToMiddle that will
- Take a reference to the head of a linked structure, an integer to add, and a number the new integer should be added after
- Create a new Node containing a reference to the integer passed to the method as an argument
- Insert the new Node after the Node containing the specified integer to be added after
- Return a reference to the head of the linked structure
- For example, calling addToMiddle(head, 99, 5), will add a Node containing a reference to 99 after the node containing a reference to the number 5
public static <T> Node<T> addToMiddle(Node<T> head, T toAdd, T addAfter) { // ... }

Verify it works as expected by adding this to the main method and running it

head = addToMiddle(head, 99, 5);
currentNode = head;
while (currentNode != null) {
    System.out.println(currentNode.getData());
    currentNode = currentNode.getNext();
}

Note

What should happen if the specified value for addAfter is not contained in the linked structure?

6.2.4. Removing from the Middle of the Structure

Write a static method in the same class as your main called removeFromMiddle that will
- Take a reference to the head of a linked structure and a value to be removed from the linked structure
- Remove the Node containing a reference to the specified value to be removed from the structure
- Return a reference to the head of the linked structure
public static <T> Node<T> removeFromMiddle(Node<T> head, T toRemove) { // ... }

Verify it works as expected by adding this to the main method and running it

head = removeFromMiddle(head, 99) ;
currentNode = head;
while (currentNode != null) {
    System.out.println(currentNode.getData());
    currentNode = currentNode.getNext();
}

Note

What should happen if the specified value for toRemove is not contained in the linked structure?

6. Linked Structures

6.1. Linked Structure

6.1.1. Node Class

6.1.2. Create the Linked Structure

6.2. Manipulating the Linked Structure

6.2.1. Adding to the Front of the Structure

6.2.2. Removing from the Front of the Structure

6.2.3. Adding to the Middle of the Structure

6.2.4. Removing from the Middle of the Structure

6.3. Kattis Problems