Package cs2110

Class DLinkedSeq<T>

java.lang.Object
cs2110.DLinkedSeq<T>
All Implemented Interfaces:
Seq<T>, Iterable<T>
public class DLinkedSeq<T> extends Object implements Seq<T>
A sequence of elements of type `T` implemented as a doubly-linked list. Null elements are not allowed.

  • Nested Class Summary

    Nested Classes
    Modifier and Type
    Class
    Description
    protected class 
    DLinkedSeq.DLinkedSeqIterator
    A forward iterator over a doubly-linked sequence.
    private class 
    DLinkedSeq.DNode
    A node of a doubly-linked sequence whose elements have type `T`.

  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    private DLinkedSeq<T>.DNode
    head
    First node of the doubly-linked sequence (null for empty sequence).
    private int
    size
    Number of elements in the sequence.
    private DLinkedSeq<T>.DNode
    tail
    Last node of the doubly-linked sequence (null for empty sequence).

  • Constructor Summary

    Constructors
    Constructor
    Description
    DLinkedSeq()
    Create an empty sequence.

  • Method Summary

    Modifier and Type
    Method
    Description
    void
    append(T elem)
    Add element `elem` to the end of this list.
    private void
    assertInv()
    Assert that this object satisfies its class invariants.
    boolean
    contains(T elem)
    Return whether this list contains an element equal to `elem` (according to `equals()`).
    boolean
    equals(Object other)
    Return whether this and `other` are `DLinkedSeq`s containing the same elements in the same order.
    private DLinkedSeq<T>.DNode
    firstNodeWith(T elem)
    Return the first node `n` such that `n.data.equals(elem)`, or null if this sequence does not contain `elem`.
    T
    get(int index)
    Return the element at index `index` in this list.
    int
    hashCode()
    Returns a hash code value for the object.
    void
    insertBefore(T elem, T successor)
    Insert element `elem` into the list just before the first occurrence of element `successor`.
    Iterator<T>
    iterator()
    Return an iterator over the elements of this sequence (in order).
    void
    prepend(T elem)
    Insert element `elem` at the beginning of this list.
    boolean
    remove(T elem)
    Remove the first occurrence of element `elem` (if any) from this list.
    int
    size()
    Return the number of elements in this list.
    String
    toString()
    Return a text representation of this sequence with the following format: the string starts with '[' and ends with ']'.

    Methods inherited from class java.lang.Object

    clone, finalize, getClass, notify, notifyAll, wait, wait, wait

    Methods inherited from interface java.lang.Iterable

    forEach, spliterator

  • Field Details

    • size

      private int size
      Number of elements in the sequence. Equal to the number of linked nodes reachable from `head` (including `head` itself) using `next` arrows.

    • tail

      private DLinkedSeq<T>.DNode tail
      Last node of the doubly-linked sequence (null for empty sequence). `tail.next` must be null.

  • Constructor Details

    • DLinkedSeq

      public DLinkedSeq()
      Create an empty sequence.

  • Method Details

    • assertInv

      private void assertInv()
      Assert that this object satisfies its class invariants.

    • size

      public int size()
      Description copied from interface: Seq
      Return the number of elements in this list.
      Specified by:
      size in interface Seq<T>

    • prepend

      public void prepend(T elem)
      Description copied from interface: Seq
      Insert element `elem` at the beginning of this list. Example: if the list is [8, 7, 4], prepend(2) would change the list to [2, 8, 7, 4]. Requires `elem` is not null.
      Specified by:
      prepend in interface Seq<T>

    • append

      public void append(T elem)
      Description copied from interface: Seq
      Add element `elem` to the end of this list. Example: if the list is [8, 7, 4], append(2) would change the list to [8, 7, 4, 2]. Requires `elem` is not null.
      Specified by:
      append in interface Seq<T>

    • get

      public T get(int index)
      Description copied from interface: Seq
      Return the element at index `index` in this list. The index of the first element is 0. Requires 0 <= index < size(). Will not return null.
      Specified by:
      get in interface Seq<T>

    • firstNodeWith

      private DLinkedSeq<T>.DNode firstNodeWith(T elem)
      Return the first node `n` such that `n.data.equals(elem)`, or null if this sequence does not contain `elem`.

    • contains

      public boolean contains(T elem)
      Description copied from interface: Seq
      Return whether this list contains an element equal to `elem` (according to `equals()`). Requires `elem` is not null.
      Specified by:
      contains in interface Seq<T>

    • insertBefore

      public void insertBefore(T elem, T successor)
      Description copied from interface: Seq
      Insert element `elem` into the list just before the first occurrence of element `successor`. Requires that `successor` is contained in the list and that `elem` and `successor` are not null.

      Example: If the list is [3, 8, 2], then insertBefore(1, 8) would change the list to [3, 1, 8, 2].

      Specified by:
      insertBefore in interface Seq<T>

    • remove

      public boolean remove(T elem)
      Description copied from interface: Seq
      Remove the first occurrence of element `elem` (if any) from this list. Return whether the list changed. Requires `elem` is not null.
      Specified by:
      remove in interface Seq<T>

    • equals

      public boolean equals(Object other)
      Return whether this and `other` are `DLinkedSeq`s containing the same elements in the same order. Two elements `e1` and `e2` are "the same" if `e1.equals(e2)`. Note that `DLinkedSeq` is mutable, so equivalence between two objects may change over time. See `Object.equals()` for additional guarantees.
      Overrides:
      equals in class Object

    • hashCode

      public int hashCode()
      Returns a hash code value for the object. See `Object.hashCode()` for additional guarantees.
      Overrides:
      hashCode in class Object

    • toString

      public String toString()
      Return a text representation of this sequence with the following format: the string starts with '[' and ends with ']'. In between are the string representations of each element, in sequence order, separated by ", ".

      Example: a sequence containing 4 7 8 in that order would be represented by "[4, 7, 8]".

      Example: a sequence containing two empty strings would be represented by "[, ]".

      The string representations of elements may contain the characters '[', ',', and ']'; these are not treated specially.

      Overrides:
      toString in class Object

    • iterator

      public Iterator<T> iterator()
      Return an iterator over the elements of this sequence (in order). By implementing `Iterable`, clients can use Java's "enhanced for-loops" to iterate over the elements of the sequence. Requires that the sequence not be mutated while the iterator is in use (except via a single active Iterator's `remove()` method).
      Specified by:
      iterator in interface Iterable<T>