# ADT:LinkedList

### Import List

        ADT:Storable
        IO
        Object
        Object
        RT0

Class List
EntryDesc |
LinkedListDesc | Linked-list implementation of a list.

Class Summary: EntryDesc [Detail]

      +---RT0.Object
           |
           +---Object.Object
                |
                +--ADT:LinkedList.EntryDesc

Inherited Methods
From RT0.Object: Finalize From Object.Object: Equals, HashCode, ToString

Class Summary: LinkedListDesc [Detail]

      +---RT0.Object
           |
           +---Object.Object
                |
                +---ADT:Storable.Object
                     |
                     +--ADT:LinkedList.LinkedListDesc

Linked-list implementation of a list. Objects may be efficiently added to or removed from the start or end of the list, making it useful for implementing queues.

Field Summary
size-: LONGINT Number of elements in the list.
Inherited Methods
From RT0.Object: Finalize From Object.Object: Equals, HashCode, ToString From ADT:Storable.Object: Load, Store

Type Summary
[Entry] = POINTER TO EntryDesc E
Iterator = POINTER TO IteratorDesc E
[IteratorDesc] = RECORD ... END
LinkedList = POINTER TO LinkedListDesc E

Procedure Summary
[AddBefore](E, Entry E)
Append(E) Appends the specified element obj to the end of this list.
Clear() Removes all of the elements from this list.
Contains(E): BOOLEAN Returns TRUE if this list contains the specified element.
Copy(): LinkedList E Returns a shallow copy of l.
Destroy()
Equals(Object): BOOLEAN Test if an object is equal to this list.
[FindEntry](LONGINT): Entry E
Get(LONGINT): E Returns the element at the specified position index in this list.
GetFirst(): E Returns the first element in this list
GetIterator(Iterator E): Iterator E Return an iterator positioned at the start of this list.
GetLast(): E Returns the last element in this list
HasNext(): BOOLEAN
HashCode(): LONGINT Returns a hash code value for the object.
INIT() Initializes an emtpy list
IndexOf(E): LONGINT Searches for the first occurence of the given argument, testing for equality using the Object.Object.Equals method.
Insert(LONGINT, E) Inserts the specified element obj at the specified position index in this list.
Insert(E)
IsEmpty(): BOOLEAN Tests if this list has no elements.
LastIndexOf(E): LONGINT Searches for the last occurence of the given argument, testing for equality using the Object.Object.Equals method.
Load(Reader) Loads data of l from r.
New(): LinkedList Creates a new list
[NewEntry](E, Entry E, Entry E): Entry E
Next(): E
NextIndex(): LONGINT
Prepend(E) Appends the specified element obj to the beginning of this list.
Remove(LONGINT): E Removes the element at the specified position index in this list.
Remove()
[RemoveEntry](Entry E)
RemoveFirst(): E Removes the first element in this list.
RemoveLast(): E Removes the last element in this list.
RemoveRange(LONGINT, LONGINT) Removes from this List all of the elements whose index is between fromIndex, inclusive and toIndex, exclusive.
Set(LONGINT, E) Replaces the element at the specified position index in this list with the specified element obj.
Set(E)
Size(): LONGINT Returns the number of elements in this list.
Store(Writer) Stores data of l to w.

Class Detail: EntryDesc

Class Detail: LinkedListDesc

Field Detail

### size

    FIELD size-: LONGINT

> Number of elements in the list.

Type Detail

### Entry

    TYPE [Entry] = POINTER TO EntryDescE

### Iterator

    TYPE Iterator = POINTER TO IteratorDescE

### IteratorDesc

    TYPE [IteratorDesc] = RECORD
                        END

### LinkedList

    TYPE LinkedList = POINTER TO LinkedListDescE

Procedure Detail

### AddBefore

    PROCEDURE (l: LinkedList) [AddBefore](element: E;
                        e: EntryE)

### Append

    PROCEDURE (l: LinkedList) Append(obj: E)

> Appends the specified element obj to the end of this list.

### Clear

    PROCEDURE (l: LinkedList) Clear()

> Removes all of the elements from this list. The list will be empty after this call returns.

### Contains

    PROCEDURE (l: LinkedList) Contains(obj: E): BOOLEAN

> Returns TRUE if this list contains the specified element.

### Copy

    PROCEDURE (l: LinkedList) Copy(): LinkedListE

> Returns a shallow copy of l. The elements themselves are not copied.

### Destroy

    PROCEDURE (l: LinkedList) Destroy()

### Equals

    PROCEDURE (l: LinkedList) Equals(obj: Object): BOOLEAN

> Test if an object is equal to this list. To be equal, a list must contain the same sequence of objects. In this context, "same" means that the Equals test returns true for pairs of objects at equivalent ordinal positions in the source lists.

### FindEntry

    PROCEDURE (l: LinkedList) [FindEntry](index: LONGINT): EntryE

### Get

    PROCEDURE (l: LinkedList) Get(index: LONGINT): E

> Returns the element at the specified position index in this list.

> Pre-condition: ``0 <= index`' and ``index < l.Size()`'

### GetFirst

    PROCEDURE (l: LinkedList) GetFirst(): E

> Returns the first element in this list

### GetIterator

    PROCEDURE (l: LinkedList) GetIterator(i: IteratorE): IteratorE

> Return an iterator positioned at the start of this list. If an iterator i is supplied (ie. not NIL), it will be initialised and returned as the result. Otherwise (i is NIL), a new iterator is allocated.

### GetLast

    PROCEDURE (l: LinkedList) GetLast(): E

> Returns the last element in this list

### HasNext

    PROCEDURE (i: Iterator) HasNext(): BOOLEAN

### HashCode

    PROCEDURE (l: LinkedList) HashCode(): LONGINT

> Returns a hash code value for the object. This method is supported for the benefit of dictionaries such as those provided by ADT:Dictionary.

> The general contract of Object.HashCode is:

> - Whenever it is invoked on the same object more than once during an execution of an application, the Object.HashCode method must consistently return the same integer, provided no information used in equals comparisons on the object is modified. This integer need not remain consistent from one execution of an application to another execution of the same application.

> - If two objects are equal according to the Object.Equals method, then calling the Object.HashCode method on each of the two objects must produce the same integer result.

> - It is not required that if two objects are unequal according to the Object.Equals method, then calling the Object.HashCode method on each of the two objects must produce distinct integer results. However, the programmer should be aware that producing distinct integer results for unequal objects may improve the performance of dictionaries.

> As much as is reasonably practical, the Object.HashCode method defined by class Object does return distinct integers for distinct objects. (This is typically implemented by converting the internal address of the object into an integer, but this implementation technique is not required.)

> [Description inherited from HashCode]

### INIT

    PROCEDURE (l: LinkedList) INIT()

> Initializes an emtpy list

### IndexOf

    PROCEDURE (l: LinkedList) IndexOf(obj: E): LONGINT

> Searches for the first occurence of the given argument, testing for equality using the Object.Object.Equals method. Returns -1 if the object is not found.

### Insert

    PROCEDURE (l: LinkedList) Insert(index: LONGINT;
                     obj: E)

> Inserts the specified element obj at the specified position index in this list. Shifts the element currently at that position (if any) and any subsequent elements to the right (adds one to their indices).

> Pre-condition: ``0 <= index`' and ``index <= l.Size()`'

### Insert

    PROCEDURE (i: Iterator) Insert(obj: E)

### IsEmpty

    PROCEDURE (l: LinkedList) IsEmpty(): BOOLEAN

> Tests if this list has no elements.

### LastIndexOf

    PROCEDURE (l: LinkedList) LastIndexOf(obj: E): LONGINT

> Searches for the last occurence of the given argument, testing for equality using the Object.Object.Equals method. Returns -1 if the object is not found.

### Load

    PROCEDURE (l: LinkedList) Load(r: Reader)
      RAISES Error;

> Loads data of l from r. Nested record pointers are loaded by calling the type-bound procecdure Reader.ReadObject. This procedure must be symmetric to Object.Store, or data internalization will break, causing undefined object state or program termination.

> Note: When internalizing a file with alien objects, it is possible that the type-bound procedure Object.Load is invoked more than once for a single object. Except for the results of the last call, all duplicates are discarded. Because of this, all changes by this procedure to any program state that is not part of the object l are deprecated.

> Pre-condition: This procedure is either activated by a super call, or from the procedure Reader.ReadObject.

> [Description inherited from Load]

### New

    PROCEDURE New(): LinkedList

> Creates a new list

### NewEntry

    PROCEDURE (l: LinkedList) [NewEntry](element: E;
                       next: EntryE;
                       previous: EntryE): EntryE

### Next

    PROCEDURE (i: Iterator) Next(): E

### NextIndex

    PROCEDURE (i: Iterator) NextIndex(): LONGINT

### Prepend

    PROCEDURE (l: LinkedList) Prepend(obj: E)

> Appends the specified element obj to the beginning of this list.

### Remove

    PROCEDURE (l: LinkedList) Remove(index: LONGINT): E

> Removes the element at the specified position index in this list. Shifts any subsequent elements to the left (subtracts one from their indices).

> Pre-condition: ``0 <= index`' and ``index < l.Size()`'

### Remove

    PROCEDURE (i: Iterator) Remove()

### RemoveEntry

    PROCEDURE (l: LinkedList) [RemoveEntry](e: EntryE)

### RemoveFirst

    PROCEDURE (l: LinkedList) RemoveFirst(): E

> Removes the first element in this list. Shifts any subsequent elements to the left (subtracts one from their indices).

### RemoveLast

    PROCEDURE (l: LinkedList) RemoveLast(): E

> Removes the last element in this list.

### RemoveRange

    PROCEDURE (l: LinkedList) RemoveRange(fromIndex: LONGINT;
                          toIndex: LONGINT)

> Removes from this List all of the elements whose index is between fromIndex, inclusive and toIndex, exclusive. Shifts any succeeding elements to the left (reduces their index). This call shortens the list by ``toIndex - fromIndex`' elements. (If ``toIndex = fromIndex`', this operation has no effect.)

> - ``0 <= fromIndex`' and ``fromIndex < l.Size()`'

> - ``0 <= toIndex`' and ``toIndex < l.Size()`'

> - ``toIndex-fromIndex >= 0`'

### Set

    PROCEDURE (l: LinkedList) Set(index: LONGINT;
                  obj: E)

> Replaces the element at the specified position index in this list with the specified element obj.

> Pre-condition: ``0 <= index`' and ``index < l.Size()`'

### Set

    PROCEDURE (i: Iterator) Set(obj: E)

### Size

    PROCEDURE (l: LinkedList) Size(): LONGINT

> Returns the number of elements in this list.

### Store

    PROCEDURE (l: LinkedList) Store(w: Writer)
      RAISES Error;

> Stores data of l to w. Nested record pointers are stored by calling the type-bound procedure Writer.WriteObject. The procedure is not allowed to make any changes to the global state of the program, except for calling the ``Write`' methods of the writer w. Any redefinition of this procedure must include a super call, preferably as the first statement of the procedure body.

> Pre-condition: This procedure is either activated by a super call, or from the procedure Writer.WriteObject.

> [Description inherited from Store]