Sitemap
Nerd For Tech

NFT is an Educational Media House. Our mission is to bring the invaluable knowledge and experiences of experts from all over the world to the novice. To know more about us, visit https://www.nerdfortech.org/.

Reverse a singly linked list

4 min readJul 27, 2021

--

Photo: Chain links
“Photo by Edge2Edge Media on Unsplash

A simple LinkedList implementation

import java.util.*;

public class LinkedList<T> implements Iterable<T> {
private Node head;
private Node tail;

public void add(T value) {
if (this.head != null) {
// the majority use-case: the head element exists
this.tail.next = new Node(value);
this.tail = this.tail.next;
return;
}

initFirstElement(value);
}

private void initFirstElement(T value) {
this.head = new Node(value);
this.tail = head;
}

public void addAll(List<T> values) {
values.forEach(this::add);
}

/**
* A singly linked list node
*/
private class Node {
private T value;
private Node prev = null;
private Node next = null;

private Node(T value) {
this.value = value;
}
}
}
public class LinkedList<T> implements Iterable<T> {
// ...

@Override
public Iterator<T> iterator() {
return new LinkedListIterator();
}

/**
* Iterate over elements until none are left
*/
private class LinkedListIterator implements Iterator<T> {
private Node cursor = LinkedList.this.head;

@Override
public boolean hasNext() {
return cursor != null;
}

@Override
public T next() {
try {
return cursor.value;
} finally {
cursor = cursor.next;
}
}
}
}
public class LinkedList<T> implements Iterable<T> {
// ...

@Override
public String toString() {
List<T> results = new ArrayList<>();
Iterator<T> it = this.iterator();
while (it.hasNext()) {
results.add(it.next());
}

return results.toString();
}
}
import java.util.List;

import static org.hamcrest.MatcherAssert.assertThat;
import static org.hamcrest.Matchers.equalTo;

class LinkedListTest {

@Test
void testLinkedListImplementation() {
// ARRANGE
List<Integer> input = List.of(1, 2, 3);
LinkedList<Integer> tested = new LinkedList<>();

// ACT
tested.addAll(input);
String output = tested.toString();

// ASSERT
assertThat("Expecting the same elements", output.toString(), equalTo(input.toString()));
}

@Test
void testEmptyLinkedList() {
// ARRANGE
LinkedList<Integer> tested = new LinkedList<>();

// ACT
String output = tested.toString();

// ASSERT
assertThat("Expecting an empty list", output.toString(), equalTo(List.of().toString()));
}
}

Solving the puzzle

public class LinkedList<T> implements Iterable<T> {
// ...

public LinkedList<T> reverse() {
// initialize references
Node newHead = null;
Node oldHead = this.head;
Node newTail = null;

// while there are elements we haven't seen in the original list
while (oldHead != null) {
// keep a reference to the next element in the original list
Node next = oldHead.next;

// change the direction of the elements
oldHead.next = newHead;

// oldHead becomes newHead (the reversed list's head)
newHead = oldHead;

// at this point, keep a reference to the reversed list's new tail
// we will need it later
if (newTail == null) {
newTail = newHead;
}

// advance the read element, in the original list
oldHead = next;
}

// construct the resulting linked list object
LinkedList<T> result = new LinkedList<>();
result.head = newHead;
result.tail = newTail;
return result;
}
}
class LinkedListTest {
// ...

@Test
void testReverseLinkedList() {
// ARRANGE
List<Integer> input = List.of(1, 2, 3);
LinkedList<Integer> tested = new LinkedList<>();
tested.addAll(input);

List<Integer> expected = List.of(3, 2, 1);

// ACT
String output = tested.reverse().toString();

// ASSERT
assertThat("Expecting the same elements, in reverse order", output.toString(), equalTo(expected.toString()));
}
}

--

--

Nerd For Tech
Nerd For Tech

Published in Nerd For Tech

NFT is an Educational Media House. Our mission is to bring the invaluable knowledge and experiences of experts from all over the world to the novice. To know more about us, visit https://www.nerdfortech.org/.

Mihai Bojin
Mihai Bojin

Written by Mihai Bojin

Software Engineer at heart, Manager by day, Indie Hacker at night. Writing about DevOps, Software engineering, and Cloud computing. Opinions my own.

No responses yet