Class DLinkedList<X>

java.lang.Object
Jcg.util.DLinkedList<X>
public class DLinkedList<X> extends Object
Minimal implementation of a doubly connected linked list, storing generic type elements.
It uses sentinel (dummy and empty) nodes to represent the beginning and the end of the list.
Author:
Luca Castelli Aleardi (Ecole Polytechnique, 2013)

  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    private DListNode<X>
    first
     
    private DListNode<X>
    last
     
    private int
    size
     

  • Constructor Summary

    Constructors
    Constructor
    Description
    DLinkedList()
     

  • Method Summary

    Modifier and Type
    Method
    Description
    void
    add(X el)
    Append a new element at the beginning of the list
    void
    addFirst(X el)
    Insert a new element at the beginning of the list
    void
    addLast(X el)
    Append a new element at the end of the list
    void
    append(DLinkedList<X> l2)
    Append the cells of 'l2' to the current list.
    DLinkedList<X>
    copy()
    Return a new linkedList, copy of the current list: only the content is copied (nodes are different)
    void
    delete(DListNode<X> pNode)
    Remove a given node from the list
    boolean
    equal(DLinkedList<X> list)
    Check equality between two lists: only the contents do count
    DListNode<X>
    getEnd()
    Return the end of the list: useful for iterating over the nodes
    DListNode<X>
    getFirst()
    Return the first node of the list The result is a null reference if the list is empty
    DListNode<X>
    getLast()
    Return the last node of the list The result is a null reference if the list is empty
    DListNode<X>
    getStart()
    Return the 'start' of the list: useful for creating circular lists
    void
    insertAfter(DListNode<X> pNode, X el)
    Insert a new element after a given node in the list
    void
    insertBefore(DListNode<X> pNode, X el)
    Insert a new element before a given node in the list
    boolean
    isEmpty()
    Check whether the list is empty
    int
    size()
     
    String
    toString()
    Return a String representing the list

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

  • Field Details

  • Constructor Details

    • DLinkedList

      public DLinkedList()

  • Method Details

    • copy

      public DLinkedList<X> copy()
      Return a new linkedList, copy of the current list: only the content is copied (nodes are different)

    • equal

      public boolean equal(DLinkedList<X> list)
      Check equality between two lists: only the contents do count

    • size

      public int size()

    • isEmpty

      public boolean isEmpty()
      Check whether the list is empty

    • getStart

      public DListNode<X> getStart()
      Return the 'start' of the list: useful for creating circular lists

    • getEnd

      public DListNode<X> getEnd()
      Return the end of the list: useful for iterating over the nodes

    • getFirst

      public DListNode<X> getFirst()
      Return the first node of the list The result is a null reference if the list is empty

    • getLast

      public DListNode<X> getLast()
      Return the last node of the list The result is a null reference if the list is empty

    • addFirst

      public void addFirst(X el)
      Insert a new element at the beginning of the list
      Parameters:
      el - the element to insert

    • addLast

      public void addLast(X el)
      Append a new element at the end of the list
      Parameters:
      el - the element to insert

    • add

      public void add(X el)
      Append a new element at the beginning of the list
      Parameters:
      el - the element to insert

    • append

      public void append(DLinkedList<X> l2)
      Append the cells of 'l2' to the current list. The merge is performed only when both lists are not empty.
      Remark: this operation takes only constant time.
      Warnings: -) both lists are modified
      Parameters:
      l2 - the list to be added (at the end of the current list)

    • insertAfter

      public void insertAfter(DListNode<X> pNode, X el)
      Insert a new element after a given node in the list
      Parameters:
      el - the element to insert
      nPnode - the place where the element will be inserted

    • insertBefore

      public void insertBefore(DListNode<X> pNode, X el)
      Insert a new element before a given node in the list
      Parameters:
      el - the element to insert
      nPnode - the place where the element will be inserted

    • delete

      public void delete(DListNode<X> pNode)
      Remove a given node from the list
      Parameters:
      nPnode - the node to delete

    • toString

      public String toString()
      Return a String representing the list
      Overrides:
      toString in class Object