Implementations
C++
#include <cstddef>
template <typename T> class LinkedList {
private:
// INFO: only C needs struct Node like creation, in cpp can just do Node
// so you never need that typedef thing
struct Node {
Node *next;
Node *prev;
T value;
// copy ctors on T expected, fails otherwise
// WARN: this'll copy the value and then copy it again to
// this -> value
// Node(T value) : value(value) {};
Node(const T &vaue) : value(value) {};
Node() = default;
};
Node *head_ = nullptr;
Node *tail_ = nullptr;
std::size_t size_ = 0;
public:
LinkedList() = default;
~LinkedList() { clear(); } // you can't do default, that's a mem leak
// NOTE: the const
std::size_t size() const { return size_; }
// push and pop
void push_back(const T &value) {
Node *node = new Node(value);
if (!head_) {
head_ = tail_ = node;
} else {
tail_->next = node;
node->prev = tail_;
tail_ = node;
}
size_++;
}
// NOTE: a clear as helper
void clear() {
while (head_) {
auto next = head_->next;
delete head_;
head_ = next;
}
tail_ = nullptr;
size_ = 0;
}
void pop_back() {
if (size_ <= 1) {
clear();
return;
}
// NOTE: invariant of size >= 2 ahead
Node *new_tail = tail_->prev;
delete tail_;
tail_ = new_tail;
tail_->next = nullptr;
size_--;
}
void push_front(const T &value) {
Node *node = new Node(value);
if (!head_) {
head_ = tail_ = node;
} else {
node->next = head_;
head_->prev = node;
head_ = node;
}
size_++;
}
void pop_front() {
if (size_ <= 1) {
clear();
return;
}
Node *new_head = head_->next;
delete head_;
head_ = new_head;
head_->prev = nullptr;
size_--;
}
// front for both const and non const, back will be same
T &back() { return tail_->value; }
const T &back() const { return tail_->value; }
};Java
import java.util.NoSuchElementException;
import java.util.Iterator;
final class LinkedList<T> implements Iterable<T> {
// the static here only matter for whether each node
// holds closure to the specific LinkedList or is shared across
//
// NOTE: that you could've also done it like Node{ T value }
// so each class has it's own inner class. Diff being is Node<String> shared
// or not
private static final class Node<T> {
// INFO:
// even if I do public here, since class is private
// and you cannot make a member more public than the contaning class
// it's redundant
// you don't need a private since well the linked list needs to use
// it
T value;
Node<T> next;
Node<T> prev;
Node(T value) {
this.value = value;
}
}
// the default values here are good
private Node<T> head;
private Node<T> tail;
private int size;
public int size() {
return size;
}
public void clear() {
// the gc in java can follow references and clear it all
// you don't need a list walk
head = null;
tail = null; // now nothing in code references stuff
size = 0;
}
public void addLast(T value) {
var node = new Node<>(value);
if (head == null) {
head = tail = node;
} else {
tail.next = node;
node.prev = tail;
tail = node;
}
size++;
}
public T removeLast() {
if (size == 0) {
throw new NoSuchElementException();
}
var old = tail.value;
tail = tail.prev;
// now this I can do in cpp as well
if (tail == null) {
head = null;
} else {
tail.next = null;
}
size--;
return old;
}
public void addFirst(T value) {
var node = new Node<>(value);
if (head == null) {
head = tail = node;
} else {
node.next = head;
head.prev = node;
head = node;
}
size++;
}
public T removeFirst() {
if (size == 0) {
throw new NoSuchElementException();
}
var old = head.value;
head = head.next;
if (head == null) {
tail = null;
} else {
head.prev = null;
}
size--;
return old;
}
// T first() and last are trivial
// method sigs need a real type
// it won't infer that since it implements Iterator<T> this should
// be T, cannot do diamond on return
@Override
public Iterator<T> iterator() {
// <> infers from return type
return new Iterator<>() {
// INFO: remember the head init here
private Node<T> cur = head;
// this should have @Override as good to have
// though since this'll fail compile time as a typo
// would not satisfy the interface, it's doing basicaly
// nothing at all when you know what you're adding is abstract
// still good otherwise in case you don't know or want to know
@Override
public boolean hasNext() {
return cur.next != null;
}
@Override
public T next() {
if (!hasNext()) {
throw new NoSuchElementException();
}
cur = cur.next;
return cur.value;
}
};
}
}Java (second implementation)
import java.util.NoSuchElementException;
import java.util.Iterator;
// the better linked list impl using the circular ll trick via a dummy node
class LinkedList<T> implements Iterable<T> {
private static class Node<T> {
T value;
Node<T> next;
Node<T> prev;
Node(T value) {
this.value = value;
}
}
private Node<T> root;
private int size = 0;
LinkedList() {
root = new Node<>(null);
root.next = root.prev = root; // empty invariant
}
public boolean isEmpty() {
return root.next == root;
}
// NOTE: implement the generic insert and delete and the rest should
// just call the generic ones
private void insert(Node<T> after, T val) {
// after ^ this node, insert this value
// ASSUMES after exists in this ll
// after -> ( val ) -> ... ( could be back )
var newNode = new Node<T>(val);
// link THIS to others
newNode.next = after.next;
newNode.prev = after;
// link OTHERS to THIS
// WARN:the order MATTERS for the below two
after.next.prev = newNode;
after.next = newNode;
size++;
}
public void addFirst(T val) {
insert(root, val); // insert afer the root
}
public void addLast(T val) {
insert(root.prev, val);
}
public int size() {
return size;
}
// any outside class cannot see type Node<T> anyway
private void remove(Node<T> node) {
if (isEmpty())
throw new NoSuchElementException();
// this node to be removed ^
if (node == root) {
throw new IllegalStateException();
}
var prev = node.prev;
var next = node.next;
prev.next = next;
next.prev = prev;
// WARN: my bias is to do node = null and say that this cleans up the ref
// it doesn't - the GC will clean it up NOT when this refers to none of
// others but rather when NONE of others refert to this
// node = null; THIS Is a noop, see above comment
size--;
}
public void removeFirst() {
remove(root.next);
}
public void removeLast() {
remove(root.prev);
}
private Node<T> getNode(int index) {
if (index >= size || index < 0)
throw new IndexOutOfBoundsException();
// INFO: ignoring the circular move optim
var cur = root;
while (index-- >= 0) {
cur = cur.next;
}
return cur;
}
public T get(int index) {
return getNode(index).value;
}
public void add(int index, T val) {
// getNode is NEVER expected to return the sentinel node
// and to NOT work with index == size
if (index > size || index < 0)
throw new IndexOutOfBoundsException();
if (index == size) {
addLast(val);
return;
}
var where = getNode(index);
insert(where.prev, val);
}
public void remove(int index) {
var where = getNode(index);
remove(where);
}
@Override
public Iterator<T> iterator() {
return new Iterator<>() {
private Node<T> cur = root;
@Override
public boolean hasNext() {
return cur.next != root;
}
@Override
public T next() {
if (!hasNext())
throw new NoSuchElementException();
cur = cur.next;
return cur.value;
}
};
}
}Notes
cpp
- new returns a pointer, somehow I was confused on type
- dtors are expected to be non-throwing. A throw calls std::terminate
- copy on back()
auto a = list.back(); // returns by ref and then cals copy ctor
auto& a = list.back(); // no ctor calledjava
- a public class MUST have the file as classname.java, it’s a compile error
- null is not falsy or even boolean for that matter
- Node node = something, is a raw type. Not
Node<Object>. This’ll compile fine but has no compile type generic based type checking. java won’t infer like cpp’s auto - var does inference of type from RHS. On generics it’ll be RHS
based - diamon pattern, a new Node(val) is raw type. new Node<>(val) is same as new
Node
(T) - @Override is cosmetic in java and is only for typo checking
The single sentinel NO null impl
a dummy sentinel node whose “empty” invariant is that next = prev = sentinel.