Singly linked list (Java)

From LiteratePrograms

Other implementations: C | C++ | Java

This is a simple implementation of a singly-linked list.

Contents 1 Creating and manipulating a list 1.1 Nodes 1.2 Creating a list 1.2.1 Inserting a node 1.2.2 Removing a node 2 Testing the list

Creating and manipulating a list

Nodes

Each node in the list contains the value and a simulated pointer to the next element. The value is of type int. But you can choose another type if you want to. A node with next==null is the last node in the list, perhaps the first if the list is empty.

The structure of a node is implemented into a new class called ListNode. Value and the next element are declared as private, so no other class is able to manipulate them directly. In order to manipulate them, getters and setters would be necessary.

<<structure>>=
public class ListNode {
    // variables
    private int value;
    private ListNode next;
    // constructors
    public ListNode() {
    }
    public ListNode(int value) {
        this.value = value;
    }
    public ListNode(int value, ListNode next) {
        this.value = value;
        this.next = next;
    }
    // getters and setters
    public int getValue() {
        return this.value;
    }
    public void setValue(int value) {
        this.value = value;
    }
    public ListNode getNext() {
        return this.next;
    }
    public void setNext(ListNode next) {
        this.next = next;
    }
}

Creating a list

To create a list, you have to specify your first element (root) and the maximum number of nodes. Further useful attributes and methods are the current number of nodes, the constructor of a new list and the getters and setters of the attributes (maximum and current number should not be manipulable).

<<list_header>>=
private ListNode root;
private int max = 10 // use a realistic number
private int number;
// constructor
public List() {
    this.root = null;
    this.number = 0;
}
// getters and setters
public ListNode getRoot() {
    return this.root;
}
public void setRoot(ListNode root) {
    this.root = root;
}
public int getMax() {
    return this.max
}
public int getNumber() {
    return this.number;
}

Inserting a node

You simply can create and insert several nodes into your list. Be careful: if an instance of ListNode is null, you don't have any access to the node. The following example inserts a new node at the end of the list.

<<list_insert>>=
public void insert_after(int value) {
    // used values
    ListNode tmp = new ListNode(value);
    ListNode tmp2 = root;
    // if list is empty
    // new node is root
    if(this.root == null) {
        this.root = tmp;
        return;
    }
    // if list is full
    // do not insert any further node
    if(this.number == this.max) {
        System.out.println("[insert] full list");
        return;
    }
    // find next empty space
    while(tmp2.getNext() != null)
        tmp2 = tmp2.getNext();
    tmp2.setNext(tmp);
    this.number++;
}

Otherwise you can insert a new node as a new root-node which could be more efficient but not always useful.

<<list_insert>>=
public void insert_beginning(int value) {
    // used values
    ListNode tmp = new ListNode(value, this.root);
    // if list is full
    // do not insert any further node
    if(this.number == this.max) {
        System.out.println("[insert] full list");
        return;
    }
    this.root = tmp;
    this.number++;
}

Removing a node

In Java it is simple to remove any node. You must not delete the node itself but the reference to that node (java uses garbage collection). There are many options to remove any node. You can remove the node with the greatest or smallest value, the node with a special value or a special node (for example the n-th node). The easiest way is to remove a special node by counting the nodes from zero to current number (as in arrays).

<<list_remove>>=
public void remove_nth(unsigned int n) {
    // used values
    ListNode tmp = this.root;
    if(this.root == null)
        return;
    if(n == 0) {
        this.root = this.root.getNext();
        return;
    }
    for(int i = n; i > 1; i--) {
        if(tmp.getNext() == null)
            return;
        tmp = tmp.getNext();
    }    
    tmp.setNext(tmp.getNext().getNext());
    this.number--;
}
public void remove_value_once(int value) {
    // used values
    ListNode tmp = this.root;
    if(this.root == null)
        return;
    if(this.root.getValue() == value) {
        this.root = this.root.getNext();
        return;
    }
    while(tmp.getNext().getValue() != value) {
        tmp = tmp.getNext();
        if(tmp.getNext() == null)
            return;
    tmp.setNext(tmp.getNext().getNext());    
}

Testing the list

<<slist.java>>=
public class List {
    list_header
    list_insert
    list_remove
    structure
}

Download code