LinkedList--Singly-Linked List

Class LinkedList provides a linked list data structure with a single forward link. Each object in a LinkedList must be an instance of a derived class of class Link. A user may implement such a class, or use class LinkOb to place object pointers on a LinkedList.

CONSTRUCTORS

LinkedList(): Constructs an empty LinkedList.

ADDING OBJECTS

virtual Object* add(Link& lnk)
virtual Object* add(Object& lnk)
virtual Object* addLast(Link& lnk)
virtual Object* addLast(Object& lnk): Adds lnk, which must be a derived class of Link, to the end of this LinkedList, sets the forward pointer of lnk to point to a special nilLink, and returns a pointer to lnk. An NIHCL_DBLLNK exception is raised if lnk is already linked to another LinkedList; i.e., the forward pointer of lnk is not 0.
virtual Object* addAfter(Link& afterLink, Link& newLink)
virtual Object* addAfter(Object& afterLink, Object& newLink): Adds newLink to this LinkedList by inserting it after afterLink. Both afterLink and newLink must be derived from class Link. An NIHCL_DBLLNK exception is raised if newlnk is already linked to another LinkedList; i.e., the forward pointer of newlnk is not 0. A NIHCL_MISSINGLNK exception is raised if afterLink is not on a LinkedList; i.e., the forward pointer of afterLink is 0 or the size of this LinkedList is zero. Note that afterLink is not checked to verify that it is linked to this LinkedList---the size of the wrong LinkedList will be incremented if it is not.
virtual Collection& addContentsTo(Collection& cltn) const: Adds a copy of all of the links in this LinkedList to cltn and returns a reference to cltn. Links are copied by applying copy().
virtual Object* addFirst(Link& lnk)
virtual Object* addFirst(Object& lnk): Adds lnk, which must be a derived class of Link, to the beginning of this LinkedList, and returns a pointer to lnk. An NIHCL_DBLLNK exception is raised if lnk is already linked to another LinkedList; i.e., the forward pointer of lnk is not 0.

REMOVING OBJECTS

virtual Object* remove(const Link& lnk)
virtual Object* remove(const Object& lnk): Searches this LinkedList for lnk, which must be a derived class of Link, unlink it, and returns a pointer to it. Note that the link removed is the same (i.e. isSame()) as lnk. If this LinkedList is empty, an NIHCL_CLTNEMPTY exception results, and if lnk is not on this LinkedList an NIHCL_OBNOTFOUND exception is raised.
virtual void removeAll(): Removes all the links from this LinkedList.
virtual Object* removeFirst()
virtual Object* removeLast(): Removes the first or last link from this LinkedList and returns a pointer to it. Raises an NIHCL_CLTNEMPTY exception if this LinkedList is empty. Note that removing the last link requires traversing all the links on a LinkedList.

SEARCHING

virtual unsigned hash() const: Returns a number that classes such as Set can use as a hash table probe. Class LinkedList implements hash() by exclusive ORing the results of applying hash() to all objects on the LinkedList.
virtual int indexOf(const Object& lnk) const: Returns the index of the first Link on this LinkedList that isEqual() to lnk. If no equal link is found a -1 is returned.
virtual unsigned occurrencesOf(const Object& lnk) const: Returns the number of occurrences of Link objects on this LinkedList that are isEqual() to lnk.

RELATIONAL OPERATORS

bool operator==(const LinkedList&) const
bool operator!=(const LinkedList&) const: Returns YES if the left LinkedList operand is equal to (or not equal to) the right LinkedList operand.

TESTING LINKEDLISTS

virtual bool includes(const Object& ob) const: Returns YES if a link that is isEqual() to ob is linked on this LinkedList.
virtual bool isEmpty() const: Returns YES if this LinkedList is empty.
virtual bool isEqual(const Object& lnklst) const: Returns YES if lnklst has species LinkedList, this LinkedList and lnklst are the same size, and all corresponding objects are equal, as determined by application of isEqual() to each of them.

COPYING LINKEDLISTS

virtual void deepenShallowCopy(): Converts this shallow copy to a deep copy by reinitializing this LinkedList, applying deepCopy() to all links, and adding the copies to create a new LinkedList from the copies.

INDEXING LINKEDLISTS

Object* operator[](int i)
const Object *const operator[](int i) const: Returns a pointer to the ith Link on this LinkedList. LinkedLists are indexed beginning at 0. Raises an NIHCL_INDEXRANGE exception if i is out of range.
virtual Object* first() const
virtual Object* last() const: Returns a pointer to the first (or last) Link in this LinkedList. If this LinkedList is empty, an NIHCL_CLTNEMPTY error is raised.

LINKEDLIST CAPACITY AND SIZE

virtual unsigned capacity() const
virtual unsigned size() const: Returns the number of Link objects on this LinkedList.
virtual void reSize(unsigned newSize): This is a no-op for class LinkedList.

SUPPORT FOR ITERATORS

virtual Object* doNext(Iterator& pos) const: Returns a pointer to the next link in this LinkedList, or 0 if no more links remain. The Iterator argument pos maintains the current position in the LinkedList.

LINKEDLIST SPECIES

virtual const Class* species() const: Returns a pointer to the class descriptor for class LinkedList.

PROTECTED MEMBERS

Downward Casts

virtual Link& linkCastdown(Object& lnk) const
Link* linkCastdown(Object* lnk) const: Calls Link::castdown() to convert the reference (or pointer) to lnk to a reference (or pointer) of type Link& (or Link*). Derived classes must override the definition of linkCastdown() to perform a downward cast to a subtype of Link, when adding objects to a LinkedList that are multiply derived from class Link, since the downward cast is otherwise ambiguous. [Section 13.10.5]

Object I/O

virtual void storer(OIOofd& fd) const
virtual void storer(OIOout& strm) const: Store the links on this LinkedList to fd or strm by applying storeOn() to each of them.

DISABLED MEMBER FUNCTIONS

virtual Object*& at(int i)
virtual const Object *const& at(int i) const
virtual void atAllPut(Object& ob)
virtual int indexOfSubCollection(const SeqCltn& cltn, int start =0) const
virtual void replaceFrom(int start, int stop, const SeqCltn& replacement, int startAt =0): These functions are implemented as shouldNotImplement().

EXCEPTIONS RAISED

NIHCL_DBLLNK, NIHCL_CLTNEMPTY, NIHCL_MISSINGLNK, NIHCL_OBNOTFOUND, NIHCL_INDEXRANGE

Go to the previous, next section.