Coming from an electrical engineering background, I have never really studied some of our most basic computer data structures in depth. In this episode I am visiting the linked list sharing some notes on how it works.
What is a linked list?
A linked list It’s a data structure consisting of a group of nodes linked together in sequence via a series of pointers.
Each node consists of a piece of data, along with a pointer pointing to the next piece of data in the list. That’s it!
It is one of the simplest, most basic data structures we’ve got, and it is used to build everything from common Lists, Stacks, to Queues.
What are it’s strengths?
The primary advantage of the linked list over a conventional array is that the linked list can handle the insertion and removal of elements, without having to reorganize the entire data structure.
In can do this because the link list is just a series of nodes and pointers (which means the data doesn’t have to sit in one contiguous block of memory), and when it does insert a new element, all it has to do is adjust it’s pointers before and after when the new node is to be inserted.
Also linked lists are very fast add adding, and accessing elements, at the top of the list O(1).
What are it’s weaknesses?
The downside of the linked list is that it doesn’t allow random access. Meaning you can’t just read/write the nth element in the list. To access data in the middle of the list, you need to walk the list from beginning to end, looking for the element you are after.
Then, once you’ve found it, you can return it or remove it. But this iterating through all the elements means that insertion, removal, and random access to O(n) time. Meaning it dependent on the number of elements (n) you have on your list.
Typical operations
Here is a list of the typical operations a linked list would perform. As you can see it looks very much like the implementation of a stack or queue.
How does it work
Here is a walk through of a simple linked list operations in Java.
Push
Here is our Node which holds our data and next element pointer in our list.
And this little snippet of code is the entire basis for how linked lists work.
This is the push operation. It basically adds a new element to the top of the list.
It takes the element of data you pass in e, creates a new Node with the data e along with a null representing the next element in the list.
And all the magic in how the linked list works is contained in these two little lines here.
First we take the new node we just created, and set it’s next pointer to the current head. Which would be null if this is the first item on our list.
Then we take the head (which was null), and set it to be equal to our new node.
These two seemingly simple lines little lines still make my head hurt. I find them confusing because you are setting one thing in one line and then resetting it in the other.
But once you grok this, you basically get the linked list and all it’s magic. Because all we are doing with a push is taking the new node, setting it’s next to be the current head (which in effect pushes the current head down one deeper into the stack), and then resetting the new node to be at the top via setting it to the head. Phew!
Pop
Popping is pretty easy. Here we check to see if we have an empty list by looking to see if the head == null. And if it isn’t, we grab the next node, set it to be the new head, and decrement our size count before returning the item or data of the node.
Note: The API has us return the data. Not the node. The Node is just an internal data structure we use implementing the list. I makes no sense to the outside world.
Remove
Here is where things get interesting. Here you are going to witness both an advantage of linked lists (the ability to remove items gracefully by merely changing several pointers) and a disadvantage of the linked list (having to iterate through all the elements to find the one you like).
A lot of the link list implementations start by doing checks on the head of the linked list first. Which is exactly what we do here.
First we grab the head, check to see if it contains the element we want, and remove it by repointing it to the next of the current element, while decrementing our size and returning true.
With the head handled, we now loop though the rest of the linked list, until we find the match we are looking for.
Then we basically did exactly what we did before with the header, only now we are doing it for some arbitrary node in our list.
We grab the node, re-point the previous node to the new next, and off we go.
This is both the advantage and disadvantage of the linked list. With just a few lines of code, we pulled an element from the beginning of the list, without having to remap, or shuffle, any other elements in our data structure. That is huge. And that is worth a moment of your time to appreciate.
But there is also the slight disadvantage, which is that to find our element, we needed to loop through the entire list to the very end (in the worst case). Alas such is life.
The rest
The rest of the implementation is basically variations on these themes of looping through the list, finding the element you are looking for, and adjusting pointers.
Summary
The linked list is a beautiful little data structure that powers a lot of the software you use every day under the hood. It doesn’t allow random access like an Array, but it’s a beautiful data structure for building Stacks and Lists.
To see what a professional looking LinkedList.java looks like checkout this implementation by Joshua Bloch in Java.
But to really understanding it, it’s always best to build these things from scratch on your own. And here is my implementation below.
Learn more
https://www.coursera.org/learn/data-structures/lecture/kHhgK/singly-linked-lists
https://codereview.stackexchange.com/questions/82698/singly-linked-list-in-java
Source and test
SingleLinkedList
public class SingleLinkedList<E> {
Node head;
int size;
public void push(E e) {
Node newNode = new Node(e, null);
newNode.next = head;
head = newNode;
size++;
}
public int lastIndexOf(E e) {
Node current = head;
int index = 0;
while (current.next != null) {
if (current.item == e) return index;
index++;
current = current.next;
}
// check the last node
if (current.item == e) return index;
return -1;
}
public E peek() {
Node<E> f = head;
return (f == null) ? null : f.item;
}
public E pop() {
// get the head
// assign head to it's next
// return head
if (head == null) return null;
Node<E> first = head;
head = first.next;
size--;
return first.item;
}
public boolean remove(E e) {
// walk the list from the beginning
// remove and return true if found
// return false
// head
Node prev = null;
Node current = head;
if (current.item.equals(e)) {
// make the next element the new head
head = current.next;
size--;
return true;
}
// all others
while (current.next != null) {
prev = current;
current = current.next;
if (current.item.equals(e)) {
// connect the previous node next to this nodes next
// thereby bypassing this current node we want to remove
prev.next = current.next;
size--;
return true;
}
}
return false;
}
public void set(int index, E e) {
Node newNode = new Node(e, null);
// head
if (index == 0) {
newNode.next = head.next;
head = newNode;
return;
}
// all others
// take the previous node
// attach it's next to this new node
// attach this new node to current next node
Node prev = head;
Node current = head.next;
for (int counter = 1; counter <= index; counter++) {
if (counter == index) {
prev.next = newNode;
newNode.next = current.next;
return;
} else {
prev = current;
current = current.next;
}
}
}
private static class Node<E> {
E item;
Node<E> next;
Node(E element, Node<E> next) {
this.item = element;
this.next = next;
}
}
}
/*
push() is neat because you are basically:
Creating a new node, assigning the old head value to be the next chain in the link (like adding), and the making
new node you just created the next head. So you are just bumping everything down one.
1. Creating a new node.
2. Assigning it's next to the current head (which at first is null because it is empty).
3. And then assigning this newNode to the head. So it is at the front of the list.
Then when you add the next node you repeat the process.
1. Create the new node.
2. Assign it's next to the current head of the list (the last element you added).
3. And then making this next node the head.
So you are basically constantly taking making new nodes, assigning their next to be current head.
And then assigning them to be the new head (while their next points to the old head).
And you just keep doing this.
*/
LinkedListTests
import junit.framework.Assert;
import junit.framework.TestCase;
import org.junit.Before;
import org.junit.Test;
import java.util.ArrayList;
import java.util.LinkedList;
public class LinkedListTests {
private SingleLinkedList sll;
@Before
public void setUp() throws Exception {
sll = new SingleLinkedList<Integer>();
}
@Test
public void InitalState() throws Exception {
Assert.assertNull(sll.head);
Assert.assertEquals(0, sll.size);
}
@Test
public void lastIndexOf() throws Exception {
sll.push(99);
sll.push(100);
sll.push(101);
Assert.assertEquals(2, sll.lastIndexOf(99));
Assert.assertEquals(1, sll.lastIndexOf(100));
Assert.assertEquals(0, sll.lastIndexOf(101));
}
@Test
public void peek() throws Exception {
sll.push(99);
Assert.assertEquals(99, sll.peek());
}
@Test
public void peekEmpty() throws Exception {
Assert.assertEquals(null, sll.peek());
}
@Test
public void pushAndPop() throws Exception {
sll.push(99);
sll.push(100);
sll.push(101);
Assert.assertEquals(101, sll.pop());
Assert.assertEquals(100, sll.pop());
Assert.assertEquals(99, sll.pop());
}
@Test
public void popEmptyList() throws Exception {
Assert.assertNull(sll.pop());
}
@Test
public void remove() throws Exception {
sll.push(99);
sll.push(100);
sll.push(101);
Assert.assertTrue(sll.remove(101));
Assert.assertEquals(100, sll.peek());
Assert.assertTrue(sll.remove(100));
Assert.assertEquals(99, sll.peek());
Assert.assertTrue(sll.remove(99));
Assert.assertEquals(null, sll.peek());
}
@Test
public void pushSize() throws Exception {
Assert.assertEquals(0, sll.size);
sll.push(99);
Assert.assertEquals(1, sll.size);
sll.push(100);
Assert.assertEquals(2, sll.size);
}
@Test
public void popSize() throws Exception {
sll.push(99);
sll.push(100);
Assert.assertEquals(2, sll.size);
sll.pop();
Assert.assertEquals(1, sll.size);
}
@Test
public void removeSize() throws Exception {
sll.push(99);
sll.push(100);
Assert.assertEquals(2, sll.size);
sll.remove(100);
Assert.assertEquals(1, sll.size);
}
@Test
public void setIndex() throws Exception {
sll.push(99);
sll.push(100);
sll.push(101);
sll.set(0, 49);
sll.set(1, 50);
sll.set(2, 51);
Assert.assertEquals(0, sll.lastIndexOf(49));
Assert.assertEquals(1, sll.lastIndexOf(50));
Assert.assertEquals(2, sll.lastIndexOf(51));
}
@Test
public void realLinkedList() throws Exception {
// Here are some tests written against the Java LinkedList class
LinkedList<Integer> linkedList = new LinkedList<Integer>();
linkedList.push(99);
linkedList.push(100);
linkedList.push(101);
Assert.assertEquals(2, linkedList.lastIndexOf(99));
Assert.assertEquals(1, linkedList.lastIndexOf(100));
Assert.assertEquals(0, linkedList.lastIndexOf(101));
linkedList.peek();
}
}
The Agile Warrior 
Leave a comment