Back to home

Gradle setupWriting the testsImplementing the Linked List
Java Linked List main image

Java Linked List

Basic unidirectional linked list in Java.

Gradle setup

In gradle.build:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 apply plugin: "java" apply plugin: "eclipse" apply plugin: "idea" repositories { mavenCentral() } dependencies { testCompile "junit:junit:4.12" } test { testLogging { exceptionFormat = 'full' events = ["passed", "failed", "skipped"] } }

Writing the tests

In src/test/jav/LinkedListTest.java:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 import org.junit.Ignore; import org.junit.Test; import static org.junit.Assert.assertEquals; import main.java.Node; public class LinkedListTest { @Test public void testGetFirst() { Node n1 = new Node(2); LinkedList ll = new LinkedList(n1); assertEquals(ll.getFirst(), n1); assertEquals(Double.valueOf(ll.getSize()), Double.valueOf(1)); } @Test public void testInsertFirst() { Node n1 = new Node(2); Node n2 = new Node(3); LinkedList ll = new LinkedList(n1); ll.insertFirst(n2); assertEquals(ll.getFirst(), n2); assertEquals(Double.valueOf(ll.getSize()), Double.valueOf(2)); } @Test public void testRemoveFirst() { Node n1 = new Node(2); Node n2 = new Node(3); LinkedList ll = new LinkedList(n1); ll.insertFirst(n2); ll.removeFirst(); assertEquals(ll.getFirst(), n1); assertEquals(Double.valueOf(ll.getSize()), Double.valueOf(1)); } @Test public void testClearList() { Node n1 = new Node(2); Node n2 = new Node(3); LinkedList ll = new LinkedList(n1); ll.insertFirst(n2); ll.clear(); assertEquals(ll.getFirst(), null); assertEquals(Double.valueOf(ll.getSize()), Double.valueOf(0)); } @Test public void testInsertLast() { Node n1 = new Node(2); Node n2 = new Node(3); Node n3 = new Node(10); LinkedList ll = new LinkedList(n1); ll.insertFirst(n2); ll.insertLast(n3); assertEquals(ll.getLast(), n3); assertEquals(Double.valueOf(ll.getSize()), Double.valueOf(3)); assertEquals(Double.valueOf(ll.getLast().getData()), Double.valueOf(10)); } @Test public void testRemoveLast() { Node n1 = new Node(2); Node n2 = new Node(3); Node n3 = new Node(10); LinkedList ll = new LinkedList(n1); ll.insertFirst(n2); ll.insertLast(n3); assertEquals(ll.getLast(), n3); assertEquals(Double.valueOf(ll.getSize()), Double.valueOf(3)); ll.removeLast(); assertEquals(ll.getLast(), n1); assertEquals(Double.valueOf(ll.getSize()), Double.valueOf(2)); } @Test public void testGetAt() { Node n1 = new Node(2); Node n2 = new Node(3); Node n3 = new Node(10); Node n4 = new Node(12); LinkedList ll = new LinkedList(n1); ll.insertLast(n2); ll.insertLast(n3); ll.insertLast(n4); assertEquals(Double.valueOf(ll.getSize()), Double.valueOf(4)); assertEquals(ll.getAt(2), n3); } @Test public void testInsertAt() { Node n1 = new Node(2); Node n2 = new Node(3); Node n3 = new Node(10); Node n4 = new Node(12); LinkedList ll = new LinkedList(n1); ll.insertFirst(n2); ll.insertLast(n3); assertEquals(Double.valueOf(ll.getSize()), Double.valueOf(3)); ll.insertAt(2, n4); assertEquals(Double.valueOf(ll.getSize()), Double.valueOf(4)); assertEquals(ll.getAt(2), n4); } }

Implementing the Linked List

Writing the Node class

In src/main/java/Node.java:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 package main.java; public class Node { private Integer data; private Node next; public Node(Integer data) { this.data = data; this.next = null; } public Node(Integer data, Node next) { this.data = data; this.next = next; } public void setNext(Node next) { this.next = next; } public Node getNext() { return this.next; } public void setData(Integer data) { this.data = data; } public Integer getData() { return this.data; } }

Writing the Linked List class

In src/main/java/LinkedList.java:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 import main.java.Node; /* @author Dennis O'Keeffe Methods: 1. insertFirst: Insert at the head of list 2. size: Fetch size 3. getFirst: Fetch the first node 4. getLast: Fetch the last node 5. clear: Remove all node 6. removeFirst: Remove head of list 7. removeLast: Remove last node 8. insertLast: Insert at end of list 9. getAt: Fetch node at index 10. removeAt: Remove node at index 11. insertAt: Insert at index 12. forEach: Iterate through list and run function on list */ class LinkedList { Integer size; Node head; public LinkedList() { this.size = 0; this.head = null; } public LinkedList(Node head) { this.size = 1; this.head = head; } public Integer getSize() { return this.size; } public Node getFirst() { return this.head; } public void insertFirst(Node n) { if (this.head != null) { Node tmp = this.head; this.head = n; n.setNext(tmp); } else { this.head = n; } this.size++; } public Node getLast() { if (this.head == null) { throw new NullPointerException("No items in the list"); } Node n = this.head; while (n.getNext() != null) { n = n.getNext(); } return n; } public void removeFirst() { if (this.head == null) { return; } else if (this.head != null && this.head.getNext() == null) { this.head = null; this.size--; } else { this.head = this.head.getNext(); this.size--; } } public void clear() { this.head = null; this.size = 0; } public void insertLast(Node n) { Node traversal = this.head; while (traversal.getNext() != null) { traversal = traversal.getNext(); } traversal.setNext(n); this.size++; } public void removeLast() { if (this.head == null) { return; } else if (this.head.getNext() == null) { this.head = null; this.size--; return; } Node n = this.head; while (n.getNext().getNext() != null) { n = n.getNext(); } n.setNext(null); this.size--; } public void insertAt(Integer i, Node n) { if (i == 0) { if (this.head != null) { Node tmp = this.head; this.head = n; n.setNext(tmp); this.size++; return; } else { this.head = n; this.size++; return; } } Integer count = 0; Node trav = this.head; while (count != i - 1) { if (trav.getNext() == null) { throw new NullPointerException("List out of bounds"); } trav = trav.getNext(); count++; } if (trav.getNext() != null) { Node tmp = trav.getNext(); trav.setNext(n); n.setNext(tmp); } else { trav.setNext(n); } this.size++; } public Node getAt(Integer i) { if (this.head == null) { throw new NullPointerException("No items in list"); } if (i == 0) { return this.head; } Node n = this.head; Integer count = 0; while (count != i) { if (n.getNext() == null) { throw new NullPointerException("No items left in list"); } n = n.getNext(); count++; } return n; } }

Dennis O'Keeffe

@dennisokeeffe92
  • Melbourne, Australia

Hi, I am a professional Software Engineer. Formerly of Culture Amp, UsabilityHub, Present Company and NightGuru.
I am currently working on workingoutloud.dev, Den Dribbles and LandPad .

Related articles


1,200+ PEOPLE ALREADY JOINED ❤️️

Get fresh posts + news direct to your inbox.

No spam. We only send you relevant content.