Overview of Singly Linked Lists

Published , Updated

The following post is derived from notes taken while reading through this textbook .

Although the diagram above may not make sense right away, just think of each node as holding a reference to the next node in the list. The red node holds a reference to the green node, the green node holds a reference to the blue node, and the blue node doesn't hold a reference to anything yet.

To put it simply, each node holds a reference to the next node in the list.

The red node is the head (beginning) of the list and the blue node is the tail (end) of the list.

    
        public class SinglyLinkedList {
            /** The head node. */
            private Node head;
            /** The total nunber of nodes in the list. */
            private long size;

            /**
            * Constructs a SinglyLinkedList.
            *
            * @param head
            *         The head node.
            */
            public SinglyLinkedList(final Node head) {
                this.head = head;
                size = calculateListSize(); // In-case the head already has nodes after it.
            }

            /**
            * Counts the total number of Nodes in the list.
            *
            * @return
            *         The total number of nodes in the list.
            */
            public long calculateListSize() {
                Node temp = head.getNextNode();
                long counter = 0;

                while (temp != null) {
                    counter++;
                    temp = temp.getNextNode();
                }

                return counter;
            }

            /**
            * Inserts a node at the head of the list.
            *
            * @param node
            *         The node to insert at the head of the list
            */
            public void addFirst(final Node node) {
                node.setNextNode(head);
                head = node;
                size++;
            }

            /**
            * Inserts a node at the tail of the list.
            *
            * @param node
            *         The node to insert.
            */
            public void addLast(final Node node) {
                if (head == null) {
                    head = node;
                    return;
                }

                Node temp = head;

                while (temp != null) {
                    temp = temp.getNextNode();
                }

                temp.setNextNode(node);
                size++;
            }

            /**
            * Removes the head node.
            *
            * @return
            *          The head node of the list, without any references to the rest of the list.
            */
            public Node removeFirst() {
                final Node temp = new Node(head.getStoredValue(), null);
                head = head.getNextNode();

                size--;
                return temp;
            }

            /**
            * Removes the tail node.
            *
            * @return
            *         The tail node of the list, without any references to the rest of the list.
            */
            public Node removeLast() {
                Node current = head;
                Node next = head.getNextNode();

                while (next != null) {
                    // If the node after next is null, then the
                    // next node is the tail node. So we remove it.
                    if (next.getNextNode() == null) {
                        break;
                    } else {
                        current = next;
                    }

                    next = current.getNextNode();
                }

                final Node temp = new Node<>(next.getStoredValue(), null);
                current.setNextNode(null);

                size--;
                return temp;
            }
        }
    
    
        public class Node {
            /** The value. */
            private E value;
            /** A reference to the next node. */
            private Node nextNode;

            /**
            * Construct a new Node.
            *
            * @param value
            *         The value.
            */
            public Node(final E value) {
                this.value = value;
            }

            /**
            * Construct a new Node.
            *
            * @param value
            *         The value.
            *
            * @param nextNode
            *         A reference to the next node.
            */
            public Node(final E value, final Node nextNode) {
                this.value = value;
                this.nextNode = nextNode;
            }

            public E getStoredValue() {
                return value;
            }

            public Node getNextNode() {
                return nextNode;
            }

            public void setStoredValue(final E value) {
                this.value = value;
            }

            public void setNextNode(final Node nextNode) {
                this.nextNode = nextNode;
            }
        }
    

Additional Information: