Linked list (linear list) is a common structure used for storing data of a variable length. The basic building block of a linked list is a node, which contains a stored value and a link to the next node (or null pointer, if this node is the last one in the list).
Variants
Singly linked list
The singly linked list is the most simple implementation, in which the nodes contain only a stored value and a link to the next node (last node contains data and a null pointer). Hence it is possible to traverse this structure only in one direction. The structure of the linked list itself usually contains only pointer to the first node and all new items (nodes) are inserted to the beginning of the list. A partial improvement is a second pointer to the last node of the list, which can be used to insert elements at the end of the list.
Doubly linked list
A node in doubly linked list contains not only pointer to the next node, but also pointer to the previous one. This way the implementation of the list is little bit more complicated, but this is compensated with higher flexibility of the structure (can be iterated in both directions).
Circularly linked list
Circularly linked list with the sentinel is a popular trick how to simplify implementation of the list. A special node – sentinel – is used as the first element of the list, also the last element of the list points to the sentinel (hence the list forms circle). An empty list contains only a sentinel node, which points to itself. Using this trick, operations insert at the beginning, insert in the middle and insert at the end of the list, are equivalent and thus they can be expressed by only one procedure.
Simplifying get operation
Get (find) operation can be also simplified. With the basic implementation the algorithm iterates over the array and in every step has to check, whether the current node is not the last one to avoid the null pointer exception. We can make sure that the algorithm always finds the value by additional node with the searched value (the sentinel node can be utilized for the this purpose).
Because we know, that the algorithm will find the node before the end of the list, we can omit the bounds checking. After termination of search we only have to make sure that the returned index is not the index of the additional element (if so, we return -1 to indicate that the searched value was not found).
Complexity of elementary operations
The insert at the beginning operation has asymptotic complexity. Operations get and delete have linear worst case complexity
, since they need to iterate over the list to the appropriate index.
Code
/**
* Singly linked list
* @author Pavel Micka
*/
public class LinkedList {
private Node first;
private Node last;
private int size;
/**
* Constructor
*/
public LinkedList() {
this.size = 0;
}
/**
* Insert the element at the end of the list
* @param i prvek k vlozeni
*/
public void add(int i) {
Node n = new Node(i);
if (size == 0) {
this.first = n;
this.last = n;
} else {
this.last.next = n;
this.last = n;
}
size++;
}
/**
* Return value at index i
* @param i index
* @throws IndexOutOfBoundsException if the index is greater or equal to the size of the list
* @throws IllegalArgumentException if i is negative
* @return value at index i
*/
public int get(int i) {
if (i >= size) {
throw new IndexOutOfBoundsException("Index out of bounds: " + i + ", size:" + this.size);
}
if (i < 0) {
throw new IllegalArgumentException("Index is less than 0");
}
Node curr = first;
for (int j = 0; j < i; j++) {
curr = curr.next;
}
return curr.value;
}
/**
* Deletes value at index i
* @param i index of the element to be deleted
* @throws IndexOutOfBoundsException if the index is greater or equal to the size of the list
* @throws IllegalArgumentException if i is negative
*/
public void remove(int i) {
if (i >= size) {
throw new IndexOutOfBoundsException("Index out of bounds: " + i + ", size:" + this.size);
}
if (i < 0) {
throw new IllegalArgumentException("Index is less than 0");
}
if (i == 0) {
first = first.next;
} else {
Node curr = first;
for (int j = 0; j < i - 1; j++) { //find the previous one
curr = curr.next;
}
curr.next = curr.next.next; //and step over the deleted element
if (i == size - 1) { //if we are deleting the last element
last = curr;
}
}
size--;
}
/**
* Dotaz na delku seznamu
* @return delka seznamu
*/
public int size() {
return this.size;
}
@Override
public String toString() {
StringBuilder builder = new StringBuilder();
Node curr = first;
for (int i = 0; i < this.size; i++) {
builder.append(curr.value);
builder.append(" ");
curr = curr.next;
}
return builder.toString();
}
/**
* Inner class representing a node of the linked list
*/
private class Node {
private int value;
private Node next;
private Node(int value) {
this.value = value;
}
}
}