trypots.nethome
the High Seas of Information Technology


A Singly Linked List data structure

This is an implementation of a Singly Linked List. My aim here was to create a version of a singly linked list that would lend itself to students for use in testing this structure by emphasizing simplicity and the ability to easily create millions of records. The Node constructor therefore can automatically create integer values for every Node.

This Singly Linked List also uses a list header, which is perhaps more common in C where the list header would be a pointer. For an example of a Singly Linked List without a head, see Singly Linked List - Bag.

Singly Linked List:



public class SinglyLinkedList
{
    private Node head;
    private int count;

    /**
     * constructor
     */
    public SinglyLinkedList() {

        /**
         * Creates a head node - this node is maintained as a reference to
         * the first node and never itself holds any actual node data
         * (users shouldn't know or care about this, however).  Conceptually
         * the head node is a pointer to the first node and is not itself
         * a node.  But since Java doesn't have pointers, the head node is
         * in practice also a member of class Node.  It should be referred
         * to as the head, never as a Node, and certainly never as the first
         * Node.  It is not part of the count of nodes in the linked list.
         */
        head new Node(00);
    }

    /**
     * returns true if linked list is empty, false otherwise
     */
    public boolean isEmpty(){
        return (head.next == null);
    }

    /**
     * insert a node at beginning of the linked list (this function could
     * be used to implement a linked list as a stack)
     */
    public void insert(Node node) {
        node.next head.next;
        head.next node;
        ++count;
    }

    /**
     * insert a node at the end of the linked list (this function could be
     * used to implement a linked list as a queue - in that case, also consider
     * adding a tail pointer to the list data structure to improve the
     * efficiency of insertions).
     */
    public void insertLast(Node node) {
        Node head;
        while(p.next != null) {
            p.next;
        }
        p.next node;
        ++count;
    }

    /**
     * removes and returns the first node from the linked list (this could
     * be used to implement a linked list as a stack)
     */
    public Node remove() {
        Node p;

        if((head.next) == null) {
            return null;
        }
        else {
            head.next p.next;
        }
        --count;
        return p;

    }

    /**
     * removes and returns the last node from the linked list
     */
    public Node removeLast() {

        Node head.next;
        Node head;

        //empty list
        if((head.next) == null) {
            return p;
        }
        //traverse to end and remove last node
        else {
            while(p.next != null) {
                p;
                p.next;
            }
            --count;
            q.next null;
            return p;
        }

    }

    /**
     * remove and returns a node by its value
     */
    public Node remove(int lookFor) {

        Node head.next;
        Node head;

        while(!= null && lookFor != p.value) {
            p;
            p.next;
        }
        if(!= null) {
            q.next p.next;
            --count;
        }

        return p;

    }

    /**
     * returns a node by its key value without removing it from the linked list
     */
    public Node fetch(int lookFor) {

        Node head.next;
        Node head;

        while(!= null && lookFor != p.value) {
            p;
            p.next;
        }

        return p;

    }

    public int size() {

        return count;

    }

    public String toString() {
        /* a simple string representation that includes the size of the
         * list and it's first and last node values.
         */
        if(!isEmpty()) {
            Node current head.next;
            String result "";
            result += "List size = " count " / ";
            result += "First node value = " current.value " / ";
            while(current.next != null) {
                current current.next;
                //System.out.println("" + current.value);
            }
            result += " Last node value = " current.value;
            return result;
        }
        else {
            return "List is empty.";
        }
    }

}



A Node object:

public class Node {

        private static int AutoNumberID;

        //if you prefer, make these fields private and use setter/getter methods
        public Node next;
        public int value;

        public Node() {
            //generate a node with a random key and empty value
            value = ++AutoNumberID;
        }

        public Node(int keyint value) {
            //note: No real guarantee of unique keys although we do imitate the
            //  use of an ID generator with our autonumber field.
            next null;
            this.value value;
        }

        public String toString() {
            return "" this.value;
        }

    }



Demonstration:

public class SinglyLinkedList_Tests {

    public static void main(String[] args) {

        int NUM_NODES 1000000;

        long startTime System.currentTimeMillis();
        long timeElapsed 0;

        SinglyLinkedList list new SinglyLinkedList();

        for(int 0NUM_NODES; ++i)
            list.insert(new Node());

        timeElapsed System.currentTimeMillis() - startTime;
        System.out.print("[timeElapsed: " timeElapsed "ms]");
        System.out.println(" Inserted " NUM_NODES " nodes");

        //remove first
        timeElapsed System.currentTimeMillis() - startTime;
        System.out.print("[timeElapsed: " timeElapsed "ms]");
        System.out.println(" removed first node [" list.remove() + "]");

        //remove middle
        timeElapsed System.currentTimeMillis() - startTime;
        System.out.print("[timeElapsed: " timeElapsed "ms]");
        System.out.println(" removed middle node [" list.remove(NUM_NODES 4) + "]");

        //remove middle
        timeElapsed System.currentTimeMillis() - startTime;
        System.out.print("[timeElapsed: " timeElapsed "ms]");
        System.out.println(" removed middle node [" list.remove(NUM_NODES 2) + "]");

        //remove middle
        timeElapsed System.currentTimeMillis() - startTime;
        System.out.print("[timeElapsed: " timeElapsed "ms]");
        System.out.println(" removed middle node [" list.remove(NUM_NODES 3) + "]");

        //remove last (requires a full traversal of list
        timeElapsed System.currentTimeMillis() - startTime;
        System.out.print("[timeElapsed: " timeElapsed "ms]");
        System.out.println(" removed last node [" list.removeLast() + "]");

    }

}

last modified: 28-Jan-2015
Copyright © 2015