Class DoublyLinkedList


  • public class DoublyLinkedList
    extends java.lang.Object
    A simple Doubly Linked list class, designed to avoid O(n) behaviour on insert and delete.
    Version:
    $Id: DoublyLinkedList.java 1733416 2016-03-03 07:07:13Z gadams $
    • Constructor Detail

      • DoublyLinkedList

        public DoublyLinkedList()
    • Method Detail

      • getSize

        public int getSize()
        Returns the number of elements currently in the list.
      • empty

        public void empty()
        Removes all elements from the list.
      • getHead

        public DoublyLinkedList.Node getHead()
        Get the current head element
        Returns:
        The current 'first' element in list.
      • getTail

        public DoublyLinkedList.Node getTail()
        Get the current tail element
        Returns:
        The current 'last' element in list.
      • touch

        public void touch​(DoublyLinkedList.Node nde)
        Moves nde to the head of the list (equivilent to remove(nde); add(nde); but faster.
      • add

        public void add​(DoublyLinkedList.Node nde)
        Adds nde to the head of the list. In perl this is called an 'unpop'. nde should not currently be part of any list.
        Parameters:
        nde - the node to add to the list.
      • remove

        public void remove​(DoublyLinkedList.Node nde)
        Removes nde from the list it is part of (should be this one, otherwise results are undefined). If nde is the current head element, then the next element becomes head, if there are no more elements the list becomes empty.
        Parameters:
        nde - node to remove.
      • pop

        public DoublyLinkedList.Node pop()
        Removes 'head' from list and returns it. Returns null if list is empty.
        Returns:
        current head element, next element becomes head.
      • unpush

        public DoublyLinkedList.Node unpush()
        Removes 'tail' from list and returns it. Returns null if list is empty.
        Returns:
        current tail element.