I have always liked the linked list so I decided to put together linked list implementations in my favourite programming languages. This post is about a linked list implementation in Java. I am not claiming it is the most efficient or best (or even most correct) implementation, but it conveys the basic ideas.
In general, a linked list consists of a set of nodes. Each node has some data and a link to the next node. When the link to the next node points to nothing, you’ve reached the end of the list. Simple, innit? We keep 2 references: one to the start of the list and one to the end of the list. This way, adding a node is quick.
The basic linked list I’ve written contains these operations:
- add: Add an item (or array of items) to the end of the list. Adding an item to this list in this simple implementation is O(1) in Big O notation because we keep a reference to the last node in the list and simply append to it.
- remove: Remove an item (or array of items) from the list. Items are located by equality. Complexity for removal is O(n) because the the list is iterated from the first element to the last, testing each item for equality.
- indexOf: Indicates the position of an item in the list, returning -1 if not found. Again, O(n) because of the list being iterated.
- size: Shows the number of items in the list. O(n) because of iteration.
- toString: Gives a string representation of the list.
- elementAt: Gives the position in the list of an element.
So, the linked list implementation I have produced here is in Java. I’ll explain the parts of importance. The full source is available in my GitHub repository.
Part 1: The list node
As I mentioned, the linked list is a sequence of nodes that are linked together. The list node, then, contains only 2 things: an Object containing the data item and a list node representing the next node in the list. I chose to make the ListNode class a private inner class because I don’t need classes outside of the LinkedList class accessing the ListNode class. The ListNode class is basically a Java Bean which contains a constructor, an Object representing the data stored in the node and a ListNode representing the next node in the list, and getters and setters for these member variables.
public class LinkedList { private class ListNode { private Object data; private ListNode next; public ListNode() { this.data = null; this.next = null; } public ListNode(Object inputData) { this.data = inputData; this.next = null; } public Object getData() { return data; } public void setData(Object data) { this.data = data; } public ListNode getNext() { return next; } public void setNext(ListNode next) { this.next = next; } } }
Part 2: The add() method(s)
To add a node to the list, it’s as simple as creating a new node, setting the next node of the old last node to the new node and setting the new last node to the new node. There are 2 add methods: one adds a single item and the other adds an array of items by calling the method that adds a single item multiple times.
public void add(Object inputData) { ListNode node = new ListNode(inputData); /* Make sure we cater for the case where the list is empty */ if (this.firstNode.getData() == null) { this.firstNode = node; this.lastNode = node; } else { this.lastNode.setNext(node); this.lastNode = node; } this.size++; } public void add(Object [] inputArray) { for (int i = 0; i < inputArray.length; i++) { this.add(inputArray[i]); } }
Part 3: The remove() method(s)
In order to remove an item from the list, we start at the beginning of the list and go to the next node in the list, checking the data in each node against what we are looking for, until we find a node that contains data that matches what is being searched for (or the end of the list is reached in which case nothing is done). We have to look ahead in the list though, because we really need to find the node before the matching node because we need to make sure that the previous node of the matching node now points to the next node of the matching node (effectively removing the matching node from the list). Think of it as bypass surgery for linked lists. Incidentally, this would be a lot easier with a Double linked list which has a pointer to next and previous. Perhaps I’ll implement it soon.
There are 2 remove methods: one removes a single item and the other removes an array of items by calling the method that removes a single item multiple times.
public void remove(Object inputData) { ListNode currentNode = this.firstNode; if (this.size == 0) { return; } boolean wasDeleted = false; /* Are we deleting the first node? */ if (inputData.equals(currentNode.getData())) { /* Only one node in list, be careful! */ if (currentNode.getNext() == null) { this.firstNode.setData(null); this.firstNode = new ListNode(); this.lastNode = this.firstNode; this.size--; return; } currentNode.setData(null); currentNode = currentNode.getNext(); this.firstNode = currentNode; this.size--; return; } while (true) { /* If end of list, stop */ if (currentNode == null) { wasDeleted = false; break; } /* Check if the data of the next is what we're looking for */ ListNode nextNode = currentNode.getNext(); if (nextNode != null) { if (inputData.equals(nextNode.getData())) { /* Found the right one, loop around the node */ ListNode nextNextNode = nextNode.getNext(); currentNode.setNext(nextNextNode); nextNode = null; wasDeleted = true; break; } } currentNode = currentNode.getNext(); } if (wasDeleted) { this.size--; } } public void remove(Object [] inputArray) { for (int i = 0; i < inputArray.length; i++) { this.remove(inputArray[i]); } }
Part 4: The helper method(s)
A linked list wouldn’t be much use if we didn’t have a way of checking its size, seeing what it contained and searching for items in the list.
Luckily we’ve kept track of size with adds and removes.
public int size() { return this.size; }
Printing the list is a case of iterating the list and printing the data items as we go.
public String toString() { ListNode currentNode = this.firstNode; StringBuffer buffer = new StringBuffer(); buffer.append("{"); for (int i = 0; currentNode != null; i++) { if (i > 0) { buffer.append(","); } Object dataObject = currentNode.getData(); buffer.append(dataObject == null ? "" : dataObject); currentNode = currentNode.getNext(); } buffer.append("}"); return buffer.toString(); }
Searching for contents is a case of iterating the list and checking the data item for equality (and counting items) as we go.
public Object elementAt(int inputPosition) { if (inputPosition >= this.size || inputPosition < 0) { return null; } ListNode currentNode = this.firstNode; for (int position = 0; position < inputPosition ; position++) { currentNode = currentNode.getNext(); } return currentNode.getData(); } public int indexOf(Object inputData) { ListNode currentNode = this.firstNode; int position = 0; boolean found = false; for (; ; position++) { if (currentNode == null) { break; } if (inputData.equals(currentNode.getData())) { found = true; break; } currentNode = currentNode.getNext(); } if (!found) { position = -1; } return position; }