Introduction

A self-referential class contains an instance that refers to another object of the same class type.

Programs can link self-referential objects together to form such useful structure as lists, queues, stacks and trees.

What is a Linked List?

A Linked List is a collection of self-referential class objects called nodes, connected by reference links, hence the term "linked" list.

A program access a linked list via a reference to the first node in the list, the program accesses each subsequent node via the link reference stored in the previous node, the link reference in the last node in the list is set to null.

Data is stored in a linked list dynamically, i.e, the program creates each node as necessary.

What is a Singly Linked List?

A Singly Linked List is a self-referential class objects(called nodes) that contains two references in one node; one reference holds the data and the other reference holds the address of the next node of the list.

Traversing a Singly Linked List

Traversing a singly linked list can be done in one direction only, since there is only a single link between two nodes of the same list.

What is a Node in a Linked List?

A node consists of a data value and a pointer to the address of the next node within the linked list. A node can contain data of any type, including references to objects of other classes.

Below is a comparison table I made, comparing a Linked List and an Array

Linked List	Array
Linked list is used when the number of elements to be stored are unpredictable	Array is used when the number of element to be stored are predictable
Linked list is Dynamic - length can increase or decrease as necessary	Array is Fixed - size is fixed at the time of creation and can not be altered
Linked list become full when the system runs out of memory	Array become full when the limit is reached
Linked list provides better memory utilization, it adapts to memory needs at execution time	Array is declared to contain more memory space, thereby wasting memory
Linked list insertion and deletion are faster, only two references are moved(after locating the insertion/deletion point). All existing node locations remain in their memory allocation	Array insertion and deletion can be time-consuming because all elements following the inserted or deleted element must be moved

Basic Operations

insertion - adds elements at the beginning/ending of the list
deletion - deletes an element from the beginning/ending of the list
find - searches for an element with the specified key
traversal - loops through the elements of the list and displays the data
remove - deletes an element at the specified key
peek - retrieves element at the beginning/ending of the list without deleting it, this operation does not alter the list

Insertion Operations

Insert at beginning

Outlined is the algorithm to add elements at the beginning of the list

START
Create a Node to store the data
Check if the list is empty
1. If the list is empty
2. THEN: add the data to the Node and assign the head pointer to it
3. ELSE: add the data to the node and link to the current head, assign the head to the newly created node
Increment the size counter
END

import java.util.EmptyStackException;

public class SinglyLinkedList<T> {
  private int size = 0; // Number of elements in the list
  Node<T> head = null; // Initial head value

  /* An internal Node for storing data */
  private class Node<T> {
    T data;
    Node<T> next;

    public Node(T data) {
      this.data = data;
      this.next = null;
    }
  }

  // add at beginning
  public void addToBeginning(T data){
      Node<T> newNode = new Node<>(data);
      if(!isEmpty()) {
          newNode.next = head;
      }
     head = newNode;
      size++;
  }
}

Insert at ending

START
Create a new node and assign the data
Check if the list is empty
1. If the list is empty
2. THEN point the head to the new node
3. ELSE traverse the list and find the last node
4. Point the last node to the new node
Increment the size counter
END

    // Add element to the end of the list
    public void add(T data) {
        addToEnding(data);
    }

 // add at ending
  public void addToEnding(T data) {
      Node<T> newNode = new Node<>(data);
    if (isEmpty()) {
        head = newNode;
    } else {
        Node<T> trav = head;
        while(trav.next != null) {
            trav = trav.next;
        }
        trav.next = newNode;
    }
    size++;
  }

Insert at an index

START
Check if the list is empty
1. If empty, throw empty stack exception
Check if index is < 0 or index > current list size
1. If TRUE, throw index out of bound exception
If index = 0;
1. Insert at the beginning of the list
2. RETURN
If index == size
1. Insert at the end of the list
2. RETURN
Traverse the list and find the element at the index
1. Assign the previous node's next pointer to the new node
2. Assign current node to be the adjacent node of the new node
Increment size
END

    public void insertAtIndex(T data, int index) {
        if (isEmpty()) throw new EmptyStackException();
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("Failed to insert, index out of bound: " + index);
         }
        // check for zero positional index
        if (index == 0) {
            addToBeginning(data);
            return;
         }

        // if index is the same as the list size, add element as last
        if (index == getSize()) {
            add(data);
            return;
         }
        // If provided index is neither the head nor tail, we traverse the list and add data at the specified index position 
        Node<T> newNode = new Node<>(data);

        int i;
        Node<T> trav;
        Node<T> prev = null;

        for (i = 0, trav = head; i != index; i++) {
            prev = trav;
            trav = trav.next;
         }

        if (prev.next != null) {
            prev.next = newNode;
            newNode.next = trav;
         }
        size++;
    }

isEmpty

START
If head = null
1. Return TRUE else FALSE

END

// method to check if the list is empty
public boolean isEmpty() {
 return head == null;
}

Deletion Operation

Delete at ending

START
Check if the list empty
1. If empty, throw empty stack exception
Traverse the list until the end
Grab the data at the end
Assign NULL to the second last element in the list
Decrease list size by 1
Return the grabbed data at step 4
END

 public T pop() {
        if (isEmpty()) throw new EmptyStackException();

        Node<T> trav = head;
        Node<T> prev = null;

        while (trav.next != null) {
            prev = trav;
            trav = trav.next;
        }

        T data = trav.data;

        if (prev == null) {
            head = null;
        } else {
            prev.next = null;
            trav = null;
        }
        --size;
        return data;
    }

Deleting at an index position

START
Iterate until we find the current node at position in the list.
Assign the adjacent node of current node in the list to its previous node.

END

public T popAtIndex(int index) {
     if (index > getSize()) throw new IllegalArgumentException();
     if (index == 0) return popFirst();
     if (index == getSize()) return popLast();

     int i;
     Node<T> trav;
     Node<T> prev = null;

     for (i = 0, trav = head; i != index; i++) {
         prev = trav;
         trav = trav.next;
     }

     T data = trav.data;
     prev.next = trav.next;
     trav = null;
     --size;
     return data;
 }

List Traversal

Iterate over the node list and return the data at each node.

 @Override
 public String toString() {
    if (isEmpty()) return "[]";
    Node<T> trav = head;
    StringBuilder sb = new StringBuilder().append("[");
    while (trav != null) {
        sb.append(trav.data);
        if (trav.next != null) sb.append(", ");
        trav = trav.next;
    }
    return sb.append("]").toString();
}

For the full source code, check out the GitHub repository https://github.com/chiorji/course-work/blob/2463d5418a6102a4f49555d9c37e363ee7ef2727/src/linkedlist/SinglyLinkedList.java

Implementing a Singly Linked List

Singly Linked List with Java