Package dsa.lab02.base

Interface LinkedList<Item>

Type Parameters:

Item - the item type

All Superinterfaces:

Container<Item>, DynamicSequence<Item>, Iterable<Item>, StaticSequence<Item>

All Known Implementing Classes:

DoublyLinkedList, DoublyLinkedList, SinglyLinkedList, SinglyLinkedList

public interface LinkedList<Item>
extends DynamicSequence<Item>

A linked list.

A dynamic sequence implemented using linked nodes, with O(n) iteration in at least one direction (first-to-last / last-to-first) (where n is the size) and O(1) insertion/removal at at least one end (first/last)

Nested Class Summary

Nested Classes

Modifier and Type	Interface	Description
static class	LinkedList.ForwardNodeIterator<Item>	A forward iterator over the nodes in a linked list.
static class	LinkedList.NodeIterator<Item>	An iterator over the nodes in a linked list.
static class	LinkedList.ReverseNodeIterator<Item>	A reverse iterator over the nodes in a linked list.

Nested classes/interfaces inherited from interface dsa.lab02.base.StaticSequence

StaticSequence.ForwardIterator<Item>, StaticSequence.ReverseIterator<Item>

Method Summary

Modifier and Type	Method	Description
default LinkedNode<Item>	firstNode()	Get the first node, or null if empty.
default Item	get(int index)	Get the item at the given index.
default Iterable<Item>	items()	Get a forward iterable that yields each item once.
default LinkedNode<Item>	lastNode()	Get the last node, or null if empty.
LinkedNode<Item>	node(int index)	Get the node at the given index.
default Iterable<LinkedNode<Item>>	nodes()	Get a forward iterable that yields each node once.
default Iterable<Item>	reversed()	Get a reverse iterable that yields each item once.
default Iterable<LinkedNode<Item>>	reversedNodes()	Get a reverse iterable that yields each node once.
default void	set(int index, Item item)	Set the item at the given index.

Methods inherited from interface dsa.lab02.base.Container

contains, isEmpty, iterator, size

Methods inherited from interface dsa.lab02.base.DynamicSequence

insert, insertFirst, insertLast, remove, removeFirst, removeLast

Methods inherited from interface java.lang.Iterable

forEach, spliterator

Methods inherited from interface dsa.lab02.base.StaticSequence

first, last, setFirst, setLast, swap

Method Details

node

LinkedNode<Item> node(int index)
               throws IndexOutOfBoundsException

Get the node at the given index.

Parameters:

index - the index

Returns:

the node that is at that index

Throws:

IndexOutOfBoundsException - if index < 0 or index >= n (where n is the size)

firstNode

default LinkedNode<Item> firstNode()

Get the first node, or null if empty.

Returns:

the node at index 0

lastNode

default LinkedNode<Item> lastNode()

Get the last node, or null if empty.

Returns:

the node at index n-1 (where n is the size)

get

default Item get(int index)
          throws IndexOutOfBoundsException

Description copied from interface: StaticSequence

Get the item at the given index.

Specified by:

get in interface StaticSequence<Item>

Parameters:

index - the index

Returns:

the item that is at that index

Throws:

IndexOutOfBoundsException - if index < 0 or index >= n (where n is the size)

set

default void set(int index,
 Item item)
          throws IndexOutOfBoundsException

Description copied from interface: StaticSequence

Set the item at the given index.

Replaces whatever item was there before.

Specified by:

set in interface StaticSequence<Item>

Parameters:

index - the index

item - the new item that should now be at that index

Throws:

IndexOutOfBoundsException - if index < 0 or index >= n (where n is the size)

nodes

default Iterable<LinkedNode<Item>> nodes()

Get a forward iterable that yields each node once.

The nodes are iterated over in first-to-last order (by index).

Returns:

an iterable over the nodes

reversedNodes

default Iterable<LinkedNode<Item>> reversedNodes()

Get a reverse iterable that yields each node once.

The nodes are iterated over in last-to-first order (by index).

Returns:

an iterable over the nodes

items

default Iterable<Item> items()

Description copied from interface: StaticSequence

Get a forward iterable that yields each item once.

The items are iterated over in first-to-last order (by index).

Specified by:

items in interface Container<Item>

Specified by:

items in interface StaticSequence<Item>

Returns:

an iterable over the items

reversed

default Iterable<Item> reversed()

Description copied from interface: StaticSequence

Get a reverse iterable that yields each item once.

The items are iterated over in last-to-first order (by index).

Specified by:

reversed in interface StaticSequence<Item>

Returns:

an iterable over the items