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.
new | Returns a new empty LinkedList. |
make | Creates and returns a new instance of self containing the elements passed in as vararg params. |
__eq | Returns true if both LinkedLists have the same size and contain the same elements in the same order. |
add | Adds val before the supplied node, or at the end of the LinkedList if no second parameter is specified. |
addAfter | Adds val AFTER the given node, or at the end of the LinkedList if no second parameter is specified. |
add | Adds val before the supplied node, or at the end of the LinkedList if no second parameter is specified. |
first | Returns the first element in this LinkedList. |
get | Gets the value being stored at node, or the first element in this LinkedList. |
iter | Returns an iterator over the elements of this LinkedList. |
join | Inserts the LinkedList otherList after the supplied node or concatenates it onto the end if no insert position is specified. |
last | Returns the last element of this LinkedList. |
nodeIter | Returns an iterator over the nodes of this LinkedList. |
remove | Removes node from this LinkedList. |
removeElement | Removes the first-encountered instance of val from this LinkedList. |
removeFirst | Removes the first element of this list and returns it. |
removeLast | Removes the last element of this list and returns it. |
reverseIter | Returns an iterator over the elements of this LinkedList in reverse order. |
set | Equivalent to performing node.val = val. |
size | Returns the number of elements in this LinkedList. |
splice | Removes the nodeRange [startNode..endNode] (inclusive both sides) and returns it as a list. |
test | Unit test. |
toString | Returns a string representation of sequence. |
addAll | Calls collection:add(e) for each e in iter(iterable). |
contains | Returns true if element exists in collection. |
containsAll | Returns true iff collection:contains(e) for e in iter(iterable). |
containsAny | Returns true if for collection:contains(e) for some e in iter(iterable). |
enum | Decorates another iteration to return the index of each element returned from the decorated iteration. |
removeAll | Calls sequence:removeElement(e) for e in iter(elements). |
LinkedList:new()
collections.make(self, ...)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)
LinkedList:add(val [,beforeNode])returns: the added node, which can be passed to a call to remove
synonyms: LinkedList.addBefore
LinkedList:addAfter(val [,afterNode])
LinkedList:add(val [,beforeNode])returns: the added node, which can be passed to a call to remove
synonyms: LinkedList.addBefore
LinkedList:first()If this list is empty, this method returns nil.
Example:
> a = LinkedList:make(4,3,2,1); print(a:first()) 4
LinkedList:get([node])
LinkedList:iter()The number of elements in the iteration will be equal to self:size().
LinkedList:join(otherList [,afterNode])otherList is invalidated as a result of this call. returns: self (to allow chaining -- a:join(b):join(c):join(d))
LinkedList:last()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] ])
LinkedList:remove(node)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)Returns val if it was removed successfully, otherwise nil.
LinkedList:removeFirst()If this list is empty then an error is thrown.
LinkedList:removeLast()If this list is empty then this method throws an error.
LinkedList:reverseIter()
LinkedList:set(node, val)val is returned by this call.
LinkedList:size()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)The returned list will have as its first element startNode.val and as its last element endNode.val.
LinkedList:test()
sequences.toString(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)
collections.contains(collection, element)This involves iterating through the entire collection and takes expected linear time.
collections.containsAll(collection, elements)
collections.containsAny(collection, iterable)
iter.enum(iterable [, size, stop, step])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)