There is an interview question asked about what data structure can be used to perform insertion and removal in FIFO. The answer is Singly - linked list with head and tail pointers. This motivated me to summarize the linked list structure.
Singly-Linked List with head and tail pointers
This is the answer for the above question. The singly linked list is a sequence of dynamically allocated storage elements, each containing a pointer to its successor. Keeping a second pointer, tail, which points to the last element of the list, allows the retrieve and remove elements in O(1) time.
How?
Adding at tail and remove at the head.
public class SinglyLinkedList {
protected ListNode head;
protected ListNode tail;
protected long size;
public SinglyLinkedList() {
head = null;
tail = null;
size = 0;
}
/**
* add to the head
*/
public void add(T value) {
ListNode node = new ListNode (value);
//if no node is in the list,
//set the tail to the first node added to the list
if (tail == null)
tail = node;
node.setNext(head);
head = node;
size++;
}
/**
* insert a node at desired position
* @param curr
* @param toInsert
* O(n)
*/
public void insert(int index, T value) {
if (index < 0 || index > size - 1)
throw new IllegalArgumentException("index must be greater than 0 and less than number of elements in the list!");
if (index == 0) {
add(value);
return;
}
if (index == size - 1) {
addLast(value);
return;
}
ListNode toInsert = new ListNode (value);
ListNode prev = getNode(index - 1);
ListNode next = prev.getNext();
prev.setNext(toInsert);
toInsert.setNext(next);
}
/**
* add the node at tail
* O(1)
*/
public void addLast(T value) {
ListNode node = new ListNode (value);
if (head == null) {
head = node;
}
else {
tail.setNext(node);
}
node.setNext(null);
tail = node;
size++;
}
/**
* remove the first element in the list
* O(n)
* @return
*/
public ListNode removeFirst() {
if (head == null)
throw new NullPointerException("Empty list!");
ListNode tmp = head;
head = head.getNext();
tmp.setNext(null);
size--;
return tmp;
}
/**
* need to traverse the list
* @return
*/
public ListNode removeLast() {
if (size == 0)
throw new NullPointerException("Empty list!");
ListNode node = head;
ListNode toRemove = tail;
while (!node.getNext().equals(tail))
node = node.getNext();
node.setNext(null);
tail = node;
size--;
return toRemove;
}
/**
* remove a node
* @param node
* O(n)
*/
public void remove(ListNode toRemove) {
if (size == 0)
throw new NullPointerException("Empty list!");
if (toRemove.equals(head))
removeFirst();
if (toRemove.equals(tail))
removeLast();
ListNode node = head;
while (node != null && !node.getNext().equals(toRemove)) {
node = node.getNext();
}
if (node == null)
throw new IllegalArgumentException("No such element in the list!");
node.setNext(node.getNext().getNext());
}
public ListNode getFirst() {
return head;
}
public ListNode getLast() {
return tail;
}
public long getSize() {
return size;
}
public void clear() {
for (ListNode node = head; node != null;) {
ListNode next = node.getNext();
node.setValue (null);
node.setNext(null);
node = next;
}
head = null;
tail = null;
size = 0;
}
public String toString() {
ListNode node = head;
String rst = "";
while (node != null) {
rst += String.valueOf(node.getValue());
rst += " -> ";
node = node.getNext();
}
return rst.substring(0, rst.length() - 4);
}
private ListNode getNode(int index) {
int count = 0;
if (index == size - 1)
return tail;
if (index == 0)
return head;
ListNode node = head;
while (count < index && node != null) {
node = node.getNext();
count++;
}
return node;
}
}
If you notice, this implementation actually can be used as a queue. However, since it is singly linked list, find any node in the list takes O(n) time.
Note that if a singly - linked list with only head pointer, it can be implemented as a stack.
(Singly) - Circular - Linked - List with a sentinel
The sentinel element is never used to hold data and it is always present. The principle is that it simplifies the programming of certain operations. E.g., we don't have to modify the head pointer. However, the disadvantage is that extra space is required.
One application for the circular linked list is to keep track of whose turn it is in a multi - player board game. Put all the players in a circular linked list, after the current player takes her turn, advance to the next player in the list. Break the cycle if the game is over.
Circular linked list can also be used as an implementation of queue. Here, we only need to maintain one pointer: the last inserted pointer. The first element is always the next of the last. Note this is also an FIFO container.
Moreover, when multiple applications are running on a PC, it is common for the OS to put the running applications on a list and then to cycle through them, giving each of them a slice of time to execute, and then making them wait while the CPU is given to another application. It is common to use a circular list so that when it reaches the end of the list, it can cycle around to the front of the list.
Note my implementation keeps track the element that has just been operated, so this cannot be used as an FIFO container.
/**
* this class implements a circular singly linked list
* since it's a circular list, there is no "head" and "tail"
* a pointer points to the current location
* any operation will set "current" to the node that has just been operated
* Note this class does not include addLast() and removeLast() method
* a "tail" pointer can be added to perform the these two operations
* @author shirleyyoung
*
* @param
*/
public class CircularSinglyLinkedList {
private ListNode sentinel;
private ListNode current;
private long size;
/**
* construct a new list
* current points to sentinel
*/
public CircularSinglyLinkedList () {
sentinel = new ListNode (null);
//current = sentinel;
//current.setNext(sentinel);
clear();
size = 0;
//System.out.println("Construct an empty list!");
//System.out.println(sentinel == null ? "sentinel equals null" : current.getValue());
}
public void clear() {
sentinel.setNext(sentinel);
current = sentinel;
size = 0;
}
/**
* insert an element after the current position
* @param value
* O(1)
*/
public void add(T value) {
ListNode node = new ListNode (value);
//System.out.println(node.getValue());
node.setNext(current.getNext());
//System.out.println(node.getNext() == null ? "Null" : node.getNext().getValue());
current.setNext(node);
//System.out.println(current.getNext() == null ? "Null" : current.getNext().getValue());
current = node;
size++;
}
/**
* add at desired position
* @param index
* @param value
* O(n)
*/
public void add(int index, T value) {
if (index < 0 || index >= size)
throw new IllegalArgumentException("Index must be greater than zero and less than list size!");
if (index == 0)
addFirst(value);
int count = 0;
ListNode node = sentinel.getNext();
while (node != sentinel && count < index - 1) {
node = node.getNext();
count++;
}
ListNode toAdd = new ListNode (value);
toAdd.setNext(node.getNext().getNext());
node.setNext(toAdd);
current = toAdd;
size++;
}
/**
* add at the head
* O(1)
* @param value
*/
public void addFirst(T value) {
current = sentinel;
add(value);
size++;
}
/**
* remove the node at current position
* makes its successor the current position
* singly linked list, need to traverse the list
* O(1)
*/
public void remove() {
if (sentinel.getNext() == sentinel)
throw new NullPointerException("Empty list!");
ListNode node = sentinel;
while (node.getNext() != current)
node = node.getNext();
node.setNext(current.getNext());
current = current.getNext();
}
/**
* if an object is in the list
* Note it returns the first occurrence of the object
* @param value
* @return
* O(n)
*/
public boolean contains(T value) {
//put the value in sentinel, if the value cannot be
//found in the list, then the node will return to sentinel
sentinel.setValue(value);
ListNode node = sentinel.getNext();
while (node.getValue() != value)
node = node.getNext();
if (node == sentinel)
return false;
sentinel.setValue(null);
//set current node to the desired node
current = node;
return true;
}
public boolean isEmpty() {
return sentinel.getNext() == sentinel;
}
/**
* return the current object
* @return
* O(1)
*/
public T getCurrent() {
if (current == sentinel)
throw new NullPointerException("Empty list!");
return current.getValue();
}
/**
* get the first object in the list
* makes the current be the head of the list
* @return
*/
public T getFirst() {
current = sentinel.getNext();
return getCurrent();
}
/**
* set the value of the current element
*/
public void setCurrent(T value) {
if (current == sentinel)
throw new NullPointerException("Empty list!");
current.setValue(value);
}
/**
* return the next object after the current element
* @return
*/
public T next() {
if (!hasNext()) {
System.err.println("No next element!");
return null;
}
current = current.getNext();
return current.getValue();
}
public boolean hasNext() {
return current.getNext() != sentinel;
}
public String toString() {
ListNode node = sentinel;
//System.out.println(node == null ? "Null" : node.getValue());
String rst = "";
node = node.getNext();
while (node != sentinel) {
rst += String.valueOf(node.getValue());
rst += " -> ";
node = node.getNext();
}
return rst.substring(0, rst.length() - 4);
}
}
Doubly - Linked -List
Java's LinkedList is a doubly linked list implementation. Doubly Linked list with both head and tail allows for add and remove from either head or tail in O(1) time, i.e., both queue and stack. However, if only head pointer is maintained, the list can be used as a stack.
Doubly linked list can be used to implement an
LRU cache.
import java.util.NoSuchElementException;
public class DoublyLinkedList {
int size;
ListNode head;
ListNode tail;
public DoublyLinkedList () {
head = null;
tail = null;
//head.next = tail;
//tail.prev = head;
size = 0;
}
/**
* add at head
* O(1)
* @param obj
*/
public void addFirst(T obj) {
ListNode h = head;
ListNode node = new ListNode (null, obj, h);
head = node;
if (tail == null)
tail = node;
else
h.prev = node;
size++;
}
/**
* add at tail
* O(1)
* @param obj
*/
public void addLast(T obj) {
ListNode t = tail;
ListNode node = new ListNode (t, obj, null);
tail = node;
if (head == null)
head = node;
else
t.next = node;
size++;
}
/**
* insert at a desired position
* O(n)
*/
public void insert(int index, T obj) {
isPositionIndex(index);
if (index == 0) {
addFirst(obj);
return;
}
if (index == size) {
addLast(obj);
return;
}
ListNode prev = getNode(index - 1);
ListNode curr = prev.next;
ListNode toAdd = new ListNode(prev, obj, curr);
curr.prev = toAdd;
prev.next = toAdd;
size++;
}
/**
* remove first element in the list
* O(1)
* @return
*/
public T removeFirst() {
if (head == null)
throw new NoSuchElementException("Probably empty list?");
T obj = head.value;
ListNode next = head.next;
head.value = null;
head.next = null;
head = next;
if (next == null)
tail = null;
else
next.prev = null;
size--;
return obj;
}
/**
* remove the last element
* O(1)
* @return
*/
public T removeLast() {
if (tail == null)
throw new NoSuchElementException("Probably empty list?");
T obj = tail.value;
ListNode prev = tail.prev;
tail.value = null;
tail.prev = null;
tail = prev;
if (prev == null)
head = null;
else
prev.next = null;
size--;
return obj;
}
/**
* remove the element at given index
* O(n)
* @param index
* @return
*/
public T remove(int index) {
isPositionIndex(index);
if (index == size)
throw new NoSuchElementException("Probably empty list?");
if (index == 0) {
return removeFirst();
}
if (index == size - 1) {
return removeLast();
}
ListNode toRemove = getNode(index);
T obj = toRemove.value;
ListNode prev = toRemove.prev;
ListNode next = toRemove.next;
prev.next = next;
next.prev = prev;
toRemove.value = null;
toRemove.prev = null;
toRemove.next = null;
size--;
return obj;
}
public T getFirst() {
if (head == null)
throw new NoSuchElementException("Probably empty list?");
return head.value;
}
public T getLast() {
if (tail == null)
throw new NoSuchElementException("Probably empty list?");
return tail.value;
}
public int getSize() {
return size;
}
public void clear() {
for (ListNode node = head; node != null;) {
ListNode next = node.next;
node.value = null;
node.next = null;
node = next;
}
head = null;
tail = null;
size = 0;
}
public String toString() {
ListNode node = head;
String rst = "";
while (node != null) {
rst += String.valueOf(node.value);
rst += " -> ";
node = node.next;
}
return rst.substring(0, rst.length() - 4);
}
private ListNode getNode(int index) {
//in the first half of the list
//traverse from the head
if (index < (size >> 1)) {
ListNode node = head;
for (int i = 0; i < index; i++)
node = node.next;
return node;
}
//in the second half
//traverse from the tail
else {
ListNode node = tail;
for (int i = size - 1; i > index; i--) {
node = node.prev;
}
return node;
}
}
private boolean isPositionIndex(int index) {
if (index < 0 || index > size)
throw new IndexOutOfBoundsException("Index must be greater than 0 and smaller than list size!");
return true;
}
}
