Build a Singly Linked List Class
Problem
Build a singly linked list (each node knows only the next node). Commands: addFirst X, addLast X (both print ok), removeFirst and removeLast (print the removed value, or empty if the list is empty), size (prints the number of elements) and print (prints the values from first to last separated by spaces, or empty). Keep a reference to the first node and to the last node.
Constraints
- 1 <= commands <= 10^4
Examples
Input
addLast 1 addLast 2 addFirst 0 print removeLast
Output
ok ok ok 0 1 2 2
Solutions
Keeping a tail reference makes addLast O(1). removeLast still needs O(n), because a singly linked node cannot go back; a doubly linked list solves this. Always handle the one-element and the empty list in every operation: they are the usual bug places.
/*
* Problem : Process lines.
* Input : Several lines.
* Output : One answer per command.
* Approach: Nodes and links.
* Time : O(1) except removeLast O(n)
* Space : O(n)
* Java : 8 or newer.
*/
import java.util.Scanner;
public class Main {
// Step 1: A node holds a value and a link to the next node. The list keeps the first node (head) and the last node (tail).
static class Node {
long value;
Node next;
Node(long value) {
this.value = value;
}
}
static class LinkedList {
private Node head = null;
private Node tail = null;
private int size = 0;
// Step 2: Adding at the front or the back changes only a few links, so it takes O(1).
void addFirst(long value) {
Node node = new Node(value);
node.next = head;
head = node;
if (tail == null) {
tail = node;
}
size++;
}
void addLast(long value) {
Node node = new Node(value);
if (tail == null) {
head = node;
} else {
tail.next = node;
}
tail = node;
size++;
}
Long removeFirst() {
if (head == null) {
return null;
}
long value = head.value;
head = head.next;
if (head == null) {
tail = null;
}
size--;
return value;
}
// Step 3: Removing the last node needs the node before it. With only a next link, we must walk from the head: O(n).
Long removeLast() {
if (head == null) {
return null;
}
if (head == tail) {
return removeFirst();
}
Node before = head;
while (before.next != tail) {
before = before.next;
}
long value = tail.value;
before.next = null;
tail = before;
size--;
return value;
}
int getSize() {
return size;
}
String show() {
if (head == null) {
return "empty";
}
StringBuilder text = new StringBuilder();
for (Node node = head; node != null; node = node.next) {
text.append(node == head ? "" : " ").append(node.value);
}
return text.toString();
}
}
// This method solves the task. It receives the input and returns the answer.
static String[] solve(String[] lines) {
LinkedList list = new LinkedList();
String[] output = new String[lines.length];
for (int i = 0; i < lines.length; i++) {
String[] part = lines[i].split(" ");
// Step 4: Run the command. A removal from an empty list gives the text empty.
if (part[0].equals("addFirst")) {
list.addFirst(Long.parseLong(part[1]));
output[i] = "ok";
} else if (part[0].equals("addLast")) {
list.addLast(Long.parseLong(part[1]));
output[i] = "ok";
} else if (part[0].equals("removeFirst") || part[0].equals("removeLast")) {
Long value = part[0].equals("removeFirst") ? list.removeFirst() : list.removeLast();
output[i] = value == null ? "empty" : String.valueOf(value);
} else if (part[0].equals("size")) {
output[i] = String.valueOf(list.getSize());
} else {
output[i] = list.show();
}
}
return output;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
java.util.List<String> all = new java.util.ArrayList<>();
while (scanner.hasNextLine()) {
String line = scanner.nextLine().trim();
if (!line.isEmpty()) {
all.add(line);
}
}
String[] lines = all.toArray(new String[0]);
System.out.println(String.join("\n", solve(lines)));
}
}
Hints (1)
- Why is removeLast slower than removeFirst?