Linked Lists
Paul Ngugi
Posted on July 19, 2024
A linked list is implemented using a linked structure. Since MyArrayList is implemented using an array, the methods get(int index) and set(int index, E e) for accessing and modifying an element through an index and the add(E e) method for adding an element at the end of the list are efficient. However, the methods add(int index, E e) and remove(int index) are inefficient, because they require shifting a potentially large number of elements. You can use a linked structure to implement a list to improve efficiency for adding and removing an element at the beginning of a list.
Nodes
In a linked list, each element is contained in an object, called the node. When a new element is added to the list, a node is created to contain it. Each node is linked to its next neighbor, as shown in Figure below.
A node can be created from a class defined as follows:
class Node<E> {
E element;
Node<E> next;
public Node(E e) {
element = e;
}
}
We use the variable head to refer to the first node in the list, and the variable tail to the last node. If the list is empty, both head and tail are null. Here is an example that creates a linked list to hold three nodes. Each node stores a string element.
Step 1: Declare head and tail.
head and tail are both null. The list is empty.
Step 2: Create the first node and append it to the list, as shown in Figure below. After the first node is inserted in the list, head and tail point to this node.
Step 3: Create the second node and append it into the list, as shown in Figure below (a). To append the second node to the list, link the first node with the new node. The new node is now the tail node, so you should move tail to point to this new node, as shown in Figure below (b).
Step 4: Create the third node and append it to the list, as shown in Figure below (a). To append the new node to the list, link the last node in the list with the new node. The new node is now the tail node, so you should move tail to point to this new node, as shown in Figure below (b).
Each node contains the element and a data field named next that points to the next element. If the node is the last in the list, its pointer data field next contains the value null. You can use this property to detect the last node. For example, you can write the following loop to traverse all the nodes in the list.
1 Node current = head;
2 while (current != null) {
3 System.out.println(current.element);
4 current = current.next;
5 }
The variable current points initially to the first node in the list (line 1). In the loop, the element of the current node is retrieved (line 3), and then current points to the next node (line 4). The loop continues until the current node is null.
The MyLinkedList Class
The MyLinkedList class uses a linked structure to implement a dynamic list. It extends MyAbstractList. In addition, it provides the methods addFirst, addLast, removeFirst, removeLast, getFirst, and getLast, as shown in Figure below.
Assuming that the class has been implemented, the code below gives a test program that uses the class.
package demo;
public class TestMyLinkedList {
public static void main(String[] args) {
// Create a list for strings
MyLinkedList<String> list = new MyLinkedList<>();
// Add elements to the list
list.add("America"); // Add it to the list
System.out.println("(1) " + list);
list.add(0, "Canada"); // Add it to the beginning of the list
System.out.println("(2) " + list);
list.add("Russia"); // Add it to the end of the list
System.out.println("(3) " + list);
list.add("France"); // Add it to the end of the list
System.out.println("(4) " + list);
list.add(2, "Germany"); // Add it to the list at index 2
System.out.println("(5) " + list);
list.add(5, "Norway"); // Add it to the list at index 5
System.out.println("(6) " + list);
list.add(0, "Poland"); // Same as list.addFirst("Poland")
System.out.println("(7) " + list);
// Remove elements from the list
list.remove(0); // Same as list.remove("Poland") in this case
System.out.println("(8) " + list);
list.remove(2); // Remove the element at index 2
System.out.println("(9) " + list);
list.remove(list.size() - 1); // Remove the last element
System.out.print("(10) " + list + "\n(11) ");
for(String s: list)
System.out.print(s.toUpperCase() + " ");
}
}
(1) [America]
(2) [Canada, America]
(3) [Canada, America, Russia]
(4) [Canada, America, Russia, France]
(5) [Canada, America, Germany, Russia, France]
(6) [Canada, America, Germany, Russia, France, Norway]
(7) [Poland, Canada, America, Germany, Russia, France, Norway]
(8) [Canada, America, Germany, Russia, France, Norway]
(9) [Canada, America, Russia, France, Norway]
(10) [Canada, America, Russia, France]
(11) CANADA AMERICA RUSSIA FRANCE
Implementing MyLinkedList
Now let us turn our attention to implementing the MyLinkedList class. We will discuss how to implement the methods addFirst, addLast, add(index, e), removeFirst, removeLast, and remove(index).
Implementing addFirst(e)
The addFirst(e) method creates a new node for holding element e. The new node becomes the first node in the list. It can be implemented as follows:
1 public void addFirst(E e) {
2 Node<E> newNode = new Node<>(e); // Create a new node
3 newNode.next = head; // link the new node with the head
4 head = newNode; // head points to the new node
5 size++; // Increase list size
6
7 if (tail == null) // The new node is the only node in list
8 tail = head;
9 }
The addFirst(e) method creates a new node to store the element (line 2) and inserts the node at the beginning of the list (line 3), as shown in Figure below (a). After the insertion, head should point to this new element node (line 4), as shown in Figure below (b).
If the list is empty (line 7), both head and tail will point to this new node (line 8). After the node is created, size should be increased by 1 (line 5).
Implementing addLast(e)
The addLast(e) method creates a node to hold the element and appends the node at the end of the list. It can be implemented as follows:
1 public void addLast(E e) {
2 Node<E> newNode = new Node<>(e); // Create a new node for e
3
4 if (tail == null) {
5 head = tail = newNode; // The only node in list
6 }
7 else {
8 tail.next = newNode; // Link the new node with the last node
9 tail = tail.next; // tail now points to the last node
10 }
11
12 size++; // Increase size
13 }
The addLast(e) method creates a new node to store the element (line 2) and appends it to the end of the list. Consider two cases:
- If the list is empty (line 4), both head and tail will point to this new node (line 5);
- Otherwise, link the node with the last node in the list (line 8). tail should now point to this new node (line 9). Figure 24.13a and Figure 24.13b show the new node for element e before and after the insertion.
In any case, after the node is created, the size should be increased by 1 (line 12).
Implementing add(index, e)
The add(index, e) method inserts an element into the list at the specified index. It can be implemented as follows:
1 public void add(int index, E e) {
2 if (index == 0) addFirst(e); // Insert first
3 else if (index >= size) addLast(e); // Insert last
4 else { // Insert in the middle
5 Node<E> current = head;
6 for (int i = 1; i < index; i++)
7 current = current.next;
8 Node<E> temp = current.next;
9 current.next = new Node<E>(e);
10 (current.next).next = temp;
11 size++;
12 }
13 }
There are three cases when inserting an element into the list:
- If index is 0, invoke addFirst(e) (line 2) to insert the element at the beginning of the list.
- If index is greater than or equal to size, invoke addLast(e) (line 3) to insert the element at the end of the list.
- Otherwise, create a new node to store the new element and locate where to insert it. As shown in Figure below (a), the new node is to be inserted between the nodes current and temp. The method assigns the new node to current.next and assigns temp to the new node’s next, as shown in Figure below (b). The size is now increased by 1 (line 11).
Implementing removeFirst()
The removeFirst() method removes the first element from the list. It can be implemented as follows:
1 public E removeFirst() {
2 if (size == 0) return null; // Nothing to delete
3 else {
4 Node<E> temp = head; // Keep the first node temporarily
5 head = head.next; // Move head to point to next node
6 size--; // Reduce size by 1
7 if (head == null) tail = null; // List becomes empty
8 return temp.element; // Return the deleted element
9 }
10 }
Consider two cases:
- If the list is empty, there is nothing to delete, so return null (line 2).
- Otherwise, remove the first node from the list by pointing head to the second node. Figure 24.15a and Figure 24.15b show the linked list before and after the deletion. The size is reduced by 1 after the deletion (line 6). If the list becomes empty, after removing the element, tail should be set to null (line 7).
Implementing removeLast()
The removeLast() method removes the last element from the list. It can be implemented as follows:
1 public E removeLast() {
2 if (size == 0) return null; // Nothing to remove
3 else if (size == 1) { // Only one element in the list
4 Node<E> temp = head;
5 head = tail = null; // list becomes empty
6 size = 0;
7 return temp.element;
8 }
9 else {
10 Node<E> current = head;
11
12 for (int i = 0; i < size - 2; i++)
13 current = current.next;
14
15 Node<E> temp = tail;
16 tail = current;
17 tail.next = null;
18 size--;
19 return temp.element;
20 }
21 }
Consider three cases:
- If the list is empty, return null (line 2).
- If the list contains only one node, this node is destroyed; head and tail both become null (line 5). The size becomes 0 after the deletion (line 6) and the element value of the deleted node is returned (line 7).
- Otherwise, the last node is destroyed (line 17) and the tail is repositioned to point to the second-to-last node. Figure below (a) and Figure below (b) show the last node before and after it is deleted. The size is reduced by 1 after the deletion (line 18) and the element value of the deleted node is returned (line 19).
Implementing remove(index)
The remove(index) method finds the node at the specified index and then removes it. It can be implemented as follows:
1 public E remove(int index) {
2 if (index < 0 || index >= size) return null; // Out of range
3 else if (index == 0) return removeFirst(); // Remove first
4 else if (index == size - 1) return removeLast(); // Remove last
5 else {
6 Node<E> previous = head;
7
8 for (int i = 1; i < index; i++) {
9 previous = previous.next;
10 }
11
12 Node<E> current = previous.next;
13 previous.next = current.next;
14 size--;
15 return current.element;
16 }
17 }
Consider four cases:
- If index is beyond the range of the list (i.e., index < 0 || index >= size), return null (line 2).
- If index is 0, invoke removeFirst() to remove the first node (line 3).
- If index is size - 1, invoke removeLast() to remove the last node (line 4).
- Otherwise, locate the node at the specified index. Let current denote this node and previous denote the node before this node, as shown in Figure below (a). Assign current.next to previous.next to eliminate the current node, as shown in Figure below (b).
The code below gives the implementation of MyLinkedList. The iterator() method defined in the java.lang.Iterable interface is implemented to return an instance on java.util.Iterator (lines 221–223). The LinkedListIterator class implements Iterator with concrete methods for hasNext, next, and remove (lines 228–256). This implementation uses current to point to the current position of the element being traversed (line 226). Initially, current points to the head of the list.
package demo;
public class MyLinkedList<E> extends MyAbstractList<E> {
private Node<E> head, tail;
/** Create a default list */
public MyLinkedList() {}
/** Create a list from an array of objects */
public MyLinkedList(E[] objects) {
super(objects);
}
/** Return the head element in the list */
public E getFirst() {
if(size == 0) {
return null;
}
else {
return head.element;
}
}
/** Return the last element in the list */
public E getLast() {
if(size == 0) {
return null;
}
else {
return tail.element;
}
}
/** Add an element to the beginning of the list */
public void addFirst(E e) {
Node<E> newNode = new Node<>(e); // Create a new node
newNode.next = head; // link the new node with the head
head = newNode; // head points to the new node
size++; // Increase list size
if (tail == null) // The new node is the only node in list
tail = head;
}
/** Add an element to the end of the list */
public void addLast(E e) {
Node<E> newNode = new Node<>(e); // Create a new node for e
if (tail == null) {
head = tail = newNode; // The only node in list
}
else {
tail.next = newNode; // Link the new node with the last node
tail = tail.next; // tail now points to the last node
}
size++; // Increase size
}
@Override /** Add a new element at the specified index
in this list. The index of the head element is 0 */
public void add(int index, E e) {
if (index == 0) addFirst(e); // Insert first
else if (index >= size) addLast(e); // Insert last
else { // Insert in the middle
Node<E> current = head;
for (int i = 1; i < index; i++)
current = current.next;
Node<E> temp = current.next;
current.next = new Node<E>(e);
(current.next).next = temp;
size++;
}
}
/** Remove the head node and
* return the object that is contained in the removed node. */
public E removeFirst() {
if (size == 0) return null; // Nothing to delete
else {
Node<E> temp = head; // Keep the first node temporarily
head = head.next; // Move head to point to next node
size--; // Reduce size by 1
if (head == null) tail = null; // List becomes empty
return temp.element; // Return the deleted element
}
}
/** Remove the last node and
* return the object that is contained in the removed node. */
public E removeLast() {
if (size == 0) return null; // Nothing to remove
else if (size == 1) { // Only one element in the list
Node<E> temp = head;
head = tail = null; // list becomes empty
size = 0;
return temp.element;
}
else {
Node<E> current = head;
for (int i = 0; i < size - 2; i++)
current = current.next;
Node<E> temp = tail;
tail = current;
tail.next = null;
size--;
return temp.element;
}
}
@Override /** Remove the element at the specified position in this
list. Return the element that was removed from the list. */
public E remove(int index) {
if (index < 0 || index >= size) return null; // Out of range
else if (index == 0) return removeFirst(); // Remove first
else if (index == size - 1) return removeLast(); // Remove last
else {
Node<E> previous = head;
for (int i = 1; i < index; i++) {
previous = previous.next;
}
Node<E> current = previous.next;
previous.next = current.next;
size--;
return current.element;
}
}
@Override
public String toString() {
StringBuilder result = new StringBuilder("[");
Node<E> current = head;
for(int i = 0; i < size; i++) {
result.append(current.element);
current = current.next;
if(current != null) {
result.append(", "); // Separate two elements with a comma
}
else {
result.append("]"); // Insert the closing } in the string
}
}
return result.toString();
}
@Override /** Clear the list */
public void clear() {
size = 0;
head = tail = null;
}
@Override /** Return true if this list contains the element e */
public boolean contains(E e) {
Node<E> current = head;
while (current != null) {
if (current.element.equals(e)) {
return true;
}
current = current.next;
}
return false;
}
@Override /** Return the element at the specified index */
public E get(int index) {
if (index < 0 || index >= size) return null; // Out of range
Node<E> current = head;
for (int i = 0; i < index; i++) {
current = current.next;
}
return current.element;
}
@Override /** Return the index of the head matching element
in this list. Return -1 if no match. */
public int indexOf(E e) {
Node<E> current = head;
for (int i = 0; i < size; i++) {
if (current.element.equals(e)) {
return i;
}
current = current.next;
}
return -1;
}
@Override /** Return the index of the last matching element
in this list. Return -1 if no match. */
public int lastIndexOf(E e) {
int index = -1;
Node<E> current = head;
for (int i = 0; i < size; i++) {
if (current.element.equals(e)) {
index = i;
}
current = current.next;
}
return index;
}
@Override /** Replace the element at the specified position
in this list with the specified element. */
public E set(int index, E e) {
if (index < 0 || index >= size) return null; // Out of range
Node<E> current = head;
for (int i = 0; i < index; i++) {
current = current.next;
}
E oldElement = current.element;
current.element = e;
return oldElement;
}
@Override /** Override iterator() defined in Iterable */
public java.util.Iterator<E> iterator() {
return new LinkedListIterator();
}
private class LinkedListIterator implements java.util.Iterator<E> {
private Node<E> current = head; // Current index
@Override
public boolean hasNext() {
return (current != null);
}
@Override
public E next() {
E e = current.element;
current = current.next;
return e;
}
@Override
public void remove() {
if (current == head) {
removeFirst();
} else {
Node<E> previous = head;
while (previous.next != current) {
previous = previous.next;
}
previous.next = current.next;
if (current == tail) {
tail = previous;
}
current = current.next;
size--;
}
}
}
// This class is only used in LinkedList, so it is private.
// This class does not need to access any
// instance members of LinkedList, so it is defined static.
private static class Node<E> {
E element;
Node<E> next;
public Node(E element) {
this.element = element;
}
}
}
MyArrayList vs. MyLinkedList
Both MyArrayList and MyLinkedList can be used to store a list. MyArrayList is implemented using an array and MyLinkedList is implemented using a linked list. The overhead of MyArrayList is smaller than that of MyLinkedList. However, MyLinkedList is more efficient if you need to insert elements into and delete elements from the beginning of the list. Table below summarizes the complexity of the methods in MyArrayList and MyLinkedList. Note that MyArrayList is the same as java.util.ArrayList and MyLinkedList is the same as java.util.LinkedList.
Variations of Linked Lists
The linked list introduced in the preceding sections is known as a singly linked list. It contains a pointer to the list’s first node, and each node contains a pointer to the next node sequentially. Several variations of the linked list are useful in certain applications.
A circular, singly linked list is like a singly linked list, except that the pointer of the last node points back to the first node, as shown in Figure below (a). Note that tail is not needed for circular linked lists. head points to the current node in the list. Insertion and deletion take place at the current node. A good application of a circular linked list is in the operating system that serves multiple users in a timesharing fashion. The system picks a user from a circular list and grants a small amount of CPU time, then moves on to the next user in the list.
A doubly linked list contains nodes with two pointers. One points to the next node and the other to the previous node, as shown in Figure below (b). These two pointers are conveniently called a forward pointer and a backward pointer. Thus, a doubly linked list can be traversed forward and backward. The java.util.LinkedList class is implemented using a doubly linked list, and it supports traversing of the list forward and backward using the ListIterator.
A circular, doubly linked list is like a doubly linked list, except that the forward pointer of the last node points to the first node and the backward pointer of the first pointer points to the last node, as shown in Figure below (c).
Posted on July 19, 2024
Join Our Newsletter. No Spam, Only the good stuff.
Sign up to receive the latest update from our blog.
Related
