양방향 연결 목록

public final class BrokenPrevLinkFailure {
    public static void main(String[] args) {
        Node a = new Node("A");
        Node c = new Node("C");
        a.next = c;
        c.prev = a;

        Node b = new Node("B");
        b.prev = a;
        b.next = c;
        a.next = b;
        // c.prev = b를 빠뜨렸다.

        System.out.println("forward=" + a.value + a.next.value + a.next.next.value);
        System.out.println("backward=" + c.value + c.prev.value);
    }

    private static final class Node {
        private final String value;
        private Node prev;
        private Node next;

        private Node(String value) {
            this.value = value;
        }
    }
}

forward=ABC
backward=CA

public final class DoublyLinkedListInvariant {
    public static void main(String[] args) {
        DoublyList<String> list = new DoublyList<>();
        list.addLast("A");
        list.addLast("C");
        list.add(1, "B");
        System.out.println("removed=" + list.remove(1));
        list.add(1, "B");
        System.out.println(list.forward());
        System.out.println(list.backward());
        System.out.println("links=" + list.linksAreValid());
    }

    private static final class DoublyList<E> {
        private Node<E> head;
        private Node<E> tail;
        private int size;

        void addLast(E value) {
            linkBefore(value, null);
        }

        void add(int index, E value) {
            checkAddIndex(index);
            linkBefore(value, index == size ? null : node(index));
        }

        private void linkBefore(E value, Node<E> successor) {
            Node<E> predecessor = successor == null ? tail : successor.prev;
            Node<E> added = new Node<>(value, predecessor, successor);
            if (predecessor == null) head = added;
            else predecessor.next = added;
            if (successor == null) tail = added;
            else successor.prev = added;
            size++;
        }

        E remove(int index) {
            Node<E> removed = node(index);
            Node<E> predecessor = removed.prev;
            Node<E> successor = removed.next;
            if (predecessor == null) head = successor;
            else predecessor.next = successor;
            if (successor == null) tail = predecessor;
            else successor.prev = predecessor;
            removed.prev = null;
            removed.next = null;
            size--;
            return removed.value;
        }

        private Node<E> node(int index) {
            checkElementIndex(index);
            if (index < size / 2) {
                Node<E> current = head;
                for (int i = 0; i < index; i++) {
                    current = current.next;
                }
                return current;
            }
            Node<E> current = tail;
            for (int i = size - 1; i > index; i--) {
                current = current.prev;
            }
            return current;
        }

        boolean linksAreValid() {
            int count = 0;
            Node<E> previous = null;
            for (Node<E> current = head; current != null; current = current.next) {
                if (current.prev != previous) return false;
                previous = current;
                count++;
            }
            return previous == tail
                    && count == size
                    && (head == null || head.prev == null)
                    && (tail == null || tail.next == null);
        }

        String forward() {
            return join(true);
        }

        String backward() {
            return join(false);
        }

        private String join(boolean forward) {
            StringBuilder out = new StringBuilder();
            for (Node<E> n = forward ? head : tail; n != null; n = forward ? n.next : n.prev) {
                if (!out.isEmpty()) out.append('-');
                out.append(n.value);
            }
            return out.toString();
        }

        private void checkElementIndex(int index) {
            if (index < 0 || index >= size) throw new IndexOutOfBoundsException(index);
        }

        private void checkAddIndex(int index) {
            if (index < 0 || index > size) throw new IndexOutOfBoundsException(index);
        }
    }

    private static final class Node<E> {
        private final E value;
        private Node<E> prev;
        private Node<E> next;

        private Node(E value, Node<E> prev, Node<E> next) {
            this.value = value;
            this.prev = prev;
            this.next = next;
        }
    }
}

DoublyList<String> list = new DoublyList<>();
list.addLast("A");
list.addLast("C");
System.out.println("tail-removed=" + list.remove(1));
System.out.println(list.forward());
System.out.println("one-links=" + list.linksAreValid());
System.out.println("last-removed=" + list.remove(0));
System.out.println("empty-links=" + list.linksAreValid());
list.add(0, "X");
System.out.println(list.backward());
System.out.println("readded-links=" + list.linksAreValid());

import java.util.LinkedList;

public final class DoublyPostRepositoryCli {
    public static void main(String[] args) {
        LinkedList<Entry> entries = new LinkedList<>();
        entries.addLast(new Entry("prev-link", 45));
        entries.addLast(new Entry("next-link", 55));
        System.out.println("oldest=" + entries.getFirst().title());
        System.out.println("newest=" + entries.getLast().title());
        int total = entries.stream().mapToInt(Entry::viewCount).sum();
        System.out.println("total=" + total);
    }

    private record Entry(String title, int viewCount) {
        private Entry {
            if (title == null || title.isBlank() || viewCount <= 0) {
                throw new IllegalArgumentException("invalid entry");
            }
        }
    }
}