Basic Data Structures #

Basic data structures are the fundamental containers to store data. They can, of course, nest with each other.

Array #

An array is a container object that holds a fixed number of values of a single type.

In the figure above, each box represents an element in the array, and the numbers above the boxes are the indices.

We can access an array with its index.

final int[] numbers = new int[10];
numbers[0] = 100;
numbers[1] = 200;
numbers[2] = 300;
numbers[9] = 1000;

System.out.println("Element at index 0: " + numbers[0]);
System.out.println("Element at index 1: " + numbers[1]);
System.out.println("Element at index 2: " + numbers[2]);
System.out.println("Element at index 7: " + numbers[7]);  // This will print 0
System.out.println("Element at index 9: " + numbers[9]);

In Java, unintialised elements in an array are set to 0.

Array supports random access, which means that we can access any element in an array in constant time. For example, accessing numbers[9] has the exact time as accessing number[0]. However, it is not easy to insert or delete elements in an array because we need to shift all elements after the insertion or deletion point.

Linked List #

A linked list is a linear data structure in which elements are stored in nodes, and each node points to the next node in the sequence.

The figure above demonstrates a simple linked list. Each node contains a data element and a pointer to the next node.

With the next pointer structure, the nodes are linked together, and we can access the linked list by starting at the head and following the next pointers until we reach the end of the list.

Now, we can write simple code to demonstrate how to implement the linked list.

In order to create a linked list, we need to first, declare the class for node.

public class Node {
  private int value = 0;    // we are storing integers
  private Node next = null;     // pointer to the next node

  // getters and setters
  public void setValue(int value) {
    this.value = value;
  }

  public int getValue() {
    return value;
  }

  public void setNext(Node next) {
    this.next = next;
  }

  public Node getNext() {
    return next;
  }
}

And we can assemble the nodes into a linked list.

public class LinkedList {
  private Node head = null;

  public Node getHead() {
    return head;
  }

  public void setHead(Node head) {
    this.head = head;
  }
}

It is important to note, that we need to store the head of the linked list in order to access the list.

Here’s a simple program to use the LinkedList class.

// create a node (node2)
Node node2 = new Node();
node2.setValue(200);

// create another node (node) in front of the node2
Node node = new Node();
node.setValue(100);
node.setNext(node2);

// assemble the nodes into a linked list
LinkedList list = new LinkedList();
list.setHead(node);

// print the value of the second node
System.out.println(list.getHead().getNext().getValue());

Double Linked List #

The regular linked list allow we to traverse the list in one direction, but sometimes we need to traverse the list in both directions.

A double linked list is similar to a linked list, but each node has two pointers: one pointing to the next node and one pointing to the previous node.

In the figure, you can see how each node is connected to both its previous and next nodes.

We can use a similar program to demonstrate how to implement the double linked list.

public class Node {
  private int value = 0;    // we are storing integers
  private Node next = null;     // pointer to the next node
  private Node prev = null;     // pointer to the prev node

  // getters and setters omitted
  ...
}

public class LinkedList {
  private Node head = null;
  private Node tail = null;     // store the pointer to the tail

  // getters and setters omitted
  ...
}

We can further use the double linked list.

// create a node (node2)
Node node2 = new Node();
node2.setValue(200);

// create another node (node) in front of the node2
Node node = new Node();
node.setValue(100);
node.setNext(node2);

// assemble the nodes into a linked list
LinkedList list = new LinkedList();
list.setHead(node);

// print the value of the first node
System.out.println(list.getTail().getPrev().getValue());

High-level data structures #

High-level data structures are data structures that are built on top of the basic data structures.

Stack #

A stack is a collection of elements, with two main principal operations:

• Push, which adds an element to the collection, and
• Pop, which removes the most recently added element.

For example, adding element 8 into the existing stack:

We can also pop out the top element from the stack:

Queue #

A queue is a collection of elements, supporting two main operations:

• Enqueue, which inserts an element to the tail, and
• Dequeue, which removes an element from the head.

In the following example, we enqueue element 5 into the existing queue:

We can also dequeue the tail element from the queue: