Data Structures: Linked Lists, Trees, Stacks and Java Code Examples

Code to Add the First Element to a Tree Structure

public void insertFirstNode(Object item) {
    // If the tree is empty, the new node becomes the root of the tree
    if (theRoot == null) {
        Node theNewNode = new Node(item);
        theRoot = theNewNode;
    }
}

Code to Delete an Element in a Linked List

public void remove(int index) {
    // Special case of removing at the head of the list
    if (index == 1) {
        head = head.getNext();
    } else {
        // Find the previous and current node
        setCurrent(index);
        prev.setNext(curr.getNext());
    }
    size = size - 1;
}

Steps to Insert an Element into a Linked List

1. Step 1: Set curr to the node at the position you want to insert.
2. Step 2: Create a new node. Set prev and next nodes to null.
3. Step 3: Copy the next link from the prev node that is already in the list into the next link of the new node. Similarly, copy the prev link from curr into the prev link of the new node.
4. Step 4: Change the next link in the prev node to point towards the new node.
5. Step 5: Change the prev link in curr to point towards the new node.

Differences Between a Single and Double Linked List

A doubly linked list (DLL) allows easy access to both the predecessor and next elements using the prev and next links of the current element. A singly linked list (SLL) allows access only to the next element.

Advantages of a Doubly Linked List Over a Singly Linked List

• A DLL allows forward and backward traversal of the linked list, while an SLL allows only forward traversal.
• A DLL uses a head pointer and a last pointer to the first and last element respectively. An SLL uses only a head pointer.

Recursive Method to Display the Height of a Binary Tree

public int h8(BTNode v) {
    if (v.isExternal()) {
        return 0;
    } else {
        return 1 + Math.max(h8(v.getLeftChild()), h8(v.getRightChild()));
    }
}

Explaining a Stack (LIFO) Using Diagrams

The Last-In-First-Out (LIFO) principle describes how objects are inserted and removed to and from a data structure. [2 Marks] This means that elements are inserted at the front (push) and removed from the front (pop). An element may be inserted at any time, but only the element which was inserted last may be removed.

Code to Find a Bus Timetable Stored in an ArrayList That Goes to Dublin

int index;
ArrayList list = new ArrayList();
if (list.contains("Dublin")) {
    index = list.indexOf("Dublin");
    System.out.println("The bus to Dublin was discovered at the index: " + index);
} else {
    System.out.println("The Dublin bus wasn't found.");
}