LinkedList

Overview

Basic doubly linked list implementation.

LinkedList can be used as a FIFO queue: add() by default appends to the end of the list (enqueue) and remove() removes by default from the front of the list (dequeue). (get() by default returns the element that would be removed next via a call to remove() and operates like a 'peek' method)

The nodes of the list are tables with fields "val", "next", and "prev".

It IS safe to modify a LinkedList while iterating, for example:

> a = LinkedList:make(iter.count(8))
> for node in a:nodeIter() do -- filter out even integers
>>  if math.mod(node.val, 2)==0 then 
>>    a:remove(node) 
>>  end
>> end
> print(a)
[1, 3, 5, 7]

Elements that are added while iterating are never seen by the iteration, even when they are added after the current node via a call to addAfter, for example:

> a = LinkedList:make(iter.count(5))
> for n in a:nodeIter() do
>>  print(n.val)
>>  a:addAfter("between", n)
>> end
1
2
3
4
5
> print(a)
[1, between, 2, between, 3, between, 4, between, 5, between]

Also see QueueVector, SkipVector.

Summary

newReturns a new empty LinkedList.
makeCreates and returns a new instance of self containing the elements passed in as vararg params.
__eqReturns true if both LinkedLists have the same size and contain the same elements in the same order.
addAdds val before the supplied node, or at the end of the LinkedList if no second parameter is specified.
addAfterAdds val AFTER the given node, or at the end of the LinkedList if no second parameter is specified.
addAdds val before the supplied node, or at the end of the LinkedList if no second parameter is specified.
firstReturns the first element in this LinkedList.
getGets the value being stored at node, or the first element in this LinkedList.
iterReturns an iterator over the elements of this LinkedList.
joinInserts the LinkedList otherList after the supplied node or concatenates it onto the end if no insert position is specified.
lastReturns the last element of this LinkedList.
nodeIterReturns an iterator over the nodes of this LinkedList.
removeRemoves node from this LinkedList.
removeElementRemoves the first-encountered instance of val from this LinkedList.
removeFirstRemoves the first element of this list and returns it.
removeLastRemoves the last element of this list and returns it.
reverseIterReturns an iterator over the elements of this LinkedList in reverse order.
setEquivalent to performing node.val = val.
sizeReturns the number of elements in this LinkedList.
spliceRemoves the nodeRange [startNode..endNode] (inclusive both sides) and returns it as a list.
testUnit test.
toStringReturns a string representation of sequence.
addAllCalls collection:add(e) for each e in iter(iterable).
containsReturns true if element exists in collection.
containsAllReturns true iff collection:contains(e) for e in iter(iterable).
containsAnyReturns true if for collection:contains(e) for some e in iter(iterable).
enumDecorates another iteration to return the index of each element returned from the decorated iteration.
removeAllCalls sequence:removeElement(e) for e in iter(elements).

Detail

LinkedList:new()

Returns a new empty LinkedList.

collections.make(self, ...)

Creates and returns a new instance of self containing the elements passed in as vararg params.

If #args is 1, the argument is assumed to be iterable and its elements are added to the Collection.

Example, assuming Collection is a sequence type:

> print( Collection:make(1,2,3,4) )
[1, 2, 3, 4]
> print( Collection:make(iter.count(4) )
[1, 2, 3, 4]
> v = Collection:make(1,2,3,4); print( Collection:make(v) )
[1, 2, 3, 4]

This method is used as the make method for LinkedList, SkipVector, HashSet, SkipSet, QueueVector, and PairingHeap. It assumes that self has new() and addAll() methods.

LinkedList:__eq(other)

Returns true if both LinkedLists have the same size and contain the same elements in the same order.

LinkedList:add(val [,beforeNode])

Adds val before the supplied node, or at the end of the LinkedList if no second parameter is specified.

returns: the added node, which can be passed to a call to remove

synonyms: LinkedList.addBefore

LinkedList:addAfter(val [,afterNode])

Adds val AFTER the given node, or at the end of the LinkedList if no second parameter is specified.

LinkedList:add(val [,beforeNode])

Adds val before the supplied node, or at the end of the LinkedList if no second parameter is specified.

returns: the added node, which can be passed to a call to remove

synonyms: LinkedList.addBefore

LinkedList:first()

Returns the first element in this LinkedList.

If this list is empty, this method returns nil.

Example:

> a = LinkedList:make(4,3,2,1); print(a:first())
4

LinkedList:get([node])

Gets the value being stored at node, or the first element in this LinkedList.

LinkedList:iter()

Returns an iterator over the elements of this LinkedList.

The number of elements in the iteration will be equal to self:size().

LinkedList:join(otherList [,afterNode])

Inserts the LinkedList otherList after the supplied node or concatenates it onto the end if no insert position is specified.

otherList is invalidated as a result of this call. returns: self (to allow chaining -- a:join(b):join(c):join(d))

LinkedList:last()

Returns the last element of this LinkedList.

If this list is empty, this method returns nil.

Example:

> a = LinkedList:make(4,3,2,1); print(a:last())
1

LinkedList:nodeIter([start [, stop] ])

Returns an iterator over the nodes of this LinkedList. The nodes returned by this iteration can be passed to a call to remove() addBefore(), or addAfter().

LinkedList:remove(node)

Removes node from this LinkedList.

Nodes can be accessed via a call to nodeIter, firstNode, lastNode, or add:

> -- assuming a == [1,2,3,4,5,6,7,8]
> for node in a:nodeIter() do -- filter out even ints
>>  if math.mod(node.val, 2) == 0 then a:remove(node) end
>> end
> print(a)
[1, 3, 5, 7]

LinkedList:removeElement(val)

Removes the first-encountered instance of val from this LinkedList.

Returns val if it was removed successfully, otherwise nil.

LinkedList:removeFirst()

Removes the first element of this list and returns it.

If this list is empty then an error is thrown.

LinkedList:removeLast()

Removes the last element of this list and returns it.

If this list is empty then this method throws an error.

LinkedList:reverseIter()

Returns an iterator over the elements of this LinkedList in reverse order.

LinkedList:set(node, val)

Equivalent to performing node.val = val.

val is returned by this call.

LinkedList:size()

Returns the number of elements in this LinkedList.

The first size()-call after a call to LinkedList:splice() will take O(size()) to compute. In all other cases it takes constant time.

LinkedList:splice(startNode, endNode)

Removes the nodeRange [startNode..endNode] (inclusive both sides) and returns it as a list.

The returned list will have as its first element startNode.val and as its last element endNode.val.

LinkedList:test()

Unit test.

sequences.toString(sequence)

Returns a string representation of sequence.

This method is used for the __tostring metamethod of Vector, SkipVector, QueueVector, and LinkedList. Example:

> print(SkipVector:make(1,2,3,4,5))
[1, 2, 3, 4, 5]

collections.addAll(collection, iterable)

Calls collection:add(e) for each e in iter(iterable).

collections.contains(collection, element)

Returns true if element exists in collection.

This involves iterating through the entire collection and takes expected linear time.

collections.containsAll(collection, elements)

Returns true iff collection:contains(e) for e in iter(iterable).

collections.containsAny(collection, iterable)

Returns true if for collection:contains(e) for some e in iter(iterable).

iter.enum(iterable [, size, stop, step])

Decorates another iteration to return the index of each element returned from the decorated iteration.

If iterable is an object with a size() method, or if size is explicitly specified, the iteration will halt after iterable:size() steps. Otherwise, the iteration halts as soon as iter(iterable) halts (this may be undesireable if the iteration is expected to contain nil values)

If 2 args are given the indices will range from 1 to arg[2]. If 3 args are given the second and third arguments are interpreted as a counting range for the enumeration; If a 4th argument is specified, args 2 and 3 specify the counting range, and arg 4 specifies the step increment.

Examples:

> for ind,v in vector("abcd"):enum() do print(ind,v) end
1       a
2       b
3       c
4       d
> vec = vector("abc"); vec:add(nil)
> for ind,v in vec:enum() do print(ind, v) end
1       a
2       b
3       c
4       nil

sequences.removeAll(sequence, elements)

Calls sequence:removeElement(e) for e in iter(elements).