com.bluegosling.collections.lists

Class UnrolledLinkedList<E>

java.lang.Object

java.util.AbstractCollection<E>

java.util.AbstractList<E>

java.util.AbstractSequentialList<E>

com.bluegosling.collections.lists.UnrolledLinkedList<E>

Type Parameters:

E - the type of element stored in the list

All Implemented Interfaces:

Serializable, Cloneable, Iterable<E>, Collection<E>, Deque<E>, List<E>, Queue<E>

public class UnrolledLinkedList<E>
extends AbstractSequentialList<E>
implements Deque<E>, Cloneable, Serializable

A list implementation that is a hybrid between a linked list and an array. To mitigate some of the performance impacts of a linked list (memory overhead, poor cache locality during traversal), this structure uses a linked list of arrays. Each node in the list represents a fixed number of list elements, stored in an array. Essentially, some number of list nodes are "unrolled" into an array.

See Also:

Wikipedia - Unrolled Linked Lists, Serialized Form

Field Summary

Fields inherited from class java.util.AbstractList

modCount

Constructor Summary

Constructors

Constructor and Description
UnrolledLinkedList() Constructs a new, empty unrolled linked list with a default unroll count of 16.
UnrolledLinkedList(Collection<? extends E> coll) Constructs a new unrolled linked list with a default unroll count of 16, populated with the elements of the specified collection.
UnrolledLinkedList(int unrollCount) Constructs a new, empty unrolled linked list with the specified unroll count.
UnrolledLinkedList(int unrollCount, Collection<? extends E> coll) Constructs a new unrolled linked list with the specified unroll count, populated with the elements of the specified collection.

Method Summary

Modifier and Type	Method and Description
boolean	add(E e)
void	add(int index, E e)
void	addFirst(E e)
void	addLast(E e)
void	clear()
UnrolledLinkedList<E>	clone()
Iterator<E>	descendingIterator()
E	element()
E	get(int index)
E	getFirst()
E	getLast()
ListIterator<E>	listIterator(int index)
boolean	offer(E e)
boolean	offerFirst(E e)
boolean	offerLast(E e)
E	peek()
E	peekFirst()
E	peekLast()
E	poll()
E	pollFirst()
E	pollLast()
E	pop()
void	push(E e)
E	remove()
E	remove(int index)
E	removeFirst()
boolean	removeFirstOccurrence(Object o)
E	removeLast()
boolean	removeLastOccurrence(Object o)
E	set(int index, E e)
int	size()

Methods inherited from class java.util.AbstractSequentialList

addAll, iterator

Methods inherited from class java.util.AbstractList

equals, hashCode, indexOf, lastIndexOf, listIterator, removeRange, subList

Methods inherited from class java.util.AbstractCollection

addAll, contains, containsAll, isEmpty, remove, removeAll, retainAll, toArray, toArray, toString

Methods inherited from class java.lang.Object

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

Methods inherited from interface java.util.Deque

contains, iterator, remove

Methods inherited from interface java.util.Collection

addAll, containsAll, equals, hashCode, isEmpty, parallelStream, removeAll, removeIf, retainAll, spliterator, stream, toArray, toArray

Methods inherited from interface java.lang.Iterable

forEach

Methods inherited from interface java.util.List

addAll, contains, containsAll, isEmpty, remove, removeAll, replaceAll, retainAll, sort, spliterator, toArray, toArray

Constructor Detail

UnrolledLinkedList

public UnrolledLinkedList()

Constructs a new, empty unrolled linked list with a default unroll count of 16.

UnrolledLinkedList

public UnrolledLinkedList(Collection<? extends E> coll)

Constructs a new unrolled linked list with a default unroll count of 16, populated with the elements of the specified collection.

Parameters:

coll - the collection of elements which will be present in the newly constructed list

UnrolledLinkedList

public UnrolledLinkedList(int unrollCount)

Constructs a new, empty unrolled linked list with the specified unroll count.

Parameters:

unrollCount - the number of elements "unrolled" into each linked list node

UnrolledLinkedList

public UnrolledLinkedList(int unrollCount,
                          Collection<? extends E> coll)

Constructs a new unrolled linked list with the specified unroll count, populated with the elements of the specified collection.

Parameters:

unrollCount - the number of elements "unrolled" into each linked list node

coll - the collection of elements which will be present in the newly constructed list

Method Detail

add

public boolean add(E e)

Specified by:

add in interface Collection<E>

Specified by:

add in interface Deque<E>

Specified by:

add in interface List<E>

Specified by:

add in interface Queue<E>

Overrides:

add in class AbstractList<E>

add

public void add(int index,
                E e)

Specified by:

add in interface List<E>

Overrides:

add in class AbstractSequentialList<E>

set

public E set(int index,
             E e)

Specified by:

set in interface List<E>

Overrides:

set in class AbstractSequentialList<E>

get

public E get(int index)

Specified by:

get in interface List<E>

Overrides:

get in class AbstractSequentialList<E>

remove

public E remove(int index)

Specified by:

remove in interface List<E>

Overrides:

remove in class AbstractSequentialList<E>

clear

public void clear()

Specified by:

clear in interface Collection<E>

Specified by:

clear in interface List<E>

Overrides:

clear in class AbstractList<E>

addFirst

public void addFirst(E e)

Specified by:

addFirst in interface Deque<E>

addLast

public void addLast(E e)

Specified by:

addLast in interface Deque<E>

offerFirst

public boolean offerFirst(E e)

Specified by:

offerFirst in interface Deque<E>

offerLast

public boolean offerLast(E e)

Specified by:

offerLast in interface Deque<E>

removeFirst

public E removeFirst()

Specified by:

removeFirst in interface Deque<E>

removeLast

public E removeLast()

Specified by:

removeLast in interface Deque<E>

pollFirst

public E pollFirst()

Specified by:

pollFirst in interface Deque<E>

pollLast

public E pollLast()

Specified by:

pollLast in interface Deque<E>

getFirst

public E getFirst()

Specified by:

getFirst in interface Deque<E>

getLast

public E getLast()

Specified by:

getLast in interface Deque<E>

peekFirst

public E peekFirst()

Specified by:

peekFirst in interface Deque<E>

peekLast

public E peekLast()

Specified by:

peekLast in interface Deque<E>

removeFirstOccurrence

public boolean removeFirstOccurrence(Object o)

Specified by:

removeFirstOccurrence in interface Deque<E>

removeLastOccurrence

public boolean removeLastOccurrence(Object o)

Specified by:

removeLastOccurrence in interface Deque<E>

offer

public boolean offer(E e)

Specified by:

offer in interface Deque<E>

Specified by:

offer in interface Queue<E>

remove

public E remove()

Specified by:

remove in interface Deque<E>

Specified by:

remove in interface Queue<E>

poll

public E poll()

Specified by:

poll in interface Deque<E>

Specified by:

poll in interface Queue<E>

element

public E element()

Specified by:

element in interface Deque<E>

Specified by:

element in interface Queue<E>

peek

public E peek()

Specified by:

peek in interface Deque<E>

Specified by:

peek in interface Queue<E>

push

public void push(E e)

Specified by:

push in interface Deque<E>

pop

public E pop()

Specified by:

pop in interface Deque<E>

descendingIterator

public Iterator<E> descendingIterator()

Specified by:

descendingIterator in interface Deque<E>

listIterator

public ListIterator<E> listIterator(int index)

Specified by:

listIterator in interface List<E>

Specified by:

listIterator in class AbstractSequentialList<E>

size

public int size()

Specified by:

size in interface Collection<E>

Specified by:

size in interface Deque<E>

Specified by:

size in interface List<E>

Specified by:

size in class AbstractCollection<E>

clone

public UnrolledLinkedList<E> clone()

Overrides:

clone in class Object