数据结构与算法学习-双向链表

双向链表

在上一篇单链表中已经提到了双向链表，其实单链表实现时候，双向链表相对容易多了，只不过对每个节点多了一个前驱节点链接，遍历可以前向遍历，也可以后向遍历。

在添加节点和删除节点时，需要注意，因为需要维护节点和前驱链和后继链，所以在添加时，先完成新节点的前向链和后向链，然后再修改新节点的前驱节点的后向链和后继节点的前驱链，分清顺序；同样，删除节点，顺序相反，先完成前驱节点和后继节点的链接，然后再修改要删除的节点的前驱链和后继链。

代码实现

public class DLinkedList<T> implements RList<T> {

    private Node<T> first;
    private Node<T> last;
    private int size;

    private static class Node<T> {
        T item;
        Node<T> prev;
        Node<T> next;

        public Node(T t, Node<T> prev, Node<T> next) {
            this.item = t;
            this.prev = prev;
            this.next = next;
        }
    }

    public void addFirst(T e) {

        Node<T> f = first;
        Node<T> newNode = new Node<>(e, null, f);
        first = newNode;
        if (f == null) {
            last = newNode;
        } else {
            f.prev = newNode;
        }
        size++;
    }

    public void addLast(T e) {

        final Node<T> l = last;
        Node<T> newNode = new Node<>(e, l, null);
        last = newNode;
        if (l == null) {
            first = newNode;
        } else {
            l.next = newNode;
        }
        size++;
    }

    @Override
    public void add(int index, T element) {
        if (isEmpty()) {
            addLast(element);
        } else {
            checkElementIndex(index);
            if (index == 0) {
                addFirst(element);
            } else if (index == size) {
                addLast(element);
            } else {
                Node<T> node = getNode(index);
                Node<T> newNode = new Node<>(element, node.prev, node);
                node.prev.next = newNode;
                node.prev = newNode;
                size++;
            }
        }

    }

    @Override
    public boolean add(T o) {
        addLast(o);
        return true;
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public boolean contains(T o) {
        return indexOf(o) != -1;
    }

    @SuppressWarnings("unchecked")
    @Override
    public T[] toArray() {
        if (isEmpty()) {
            return null;
        }
        Object[] arr = new Object[size];
        int i = 0;
        for (Node<T> node = first; node != null; node = node.next) {
            arr[i++] = node.item;
        }
        return (T[]) arr;
    }

    @Override
    public boolean remove(T o) {
        int index = indexOf(o);
        if (index == -1) {
            return false;
        }
        removeByIndex(index);
        return true;
    }

    public T removeFirst() {
        if (isEmpty()) {
            return null;
        }
        final Node<T> f = first;
        T result = f.item;
        first = f.next;
        if (first == null) {
            last = null;
        } else {
            first.prev = null;
            f.next = null;
            f.item = null;
        }
        size--;
        return result;
    }

    public T removeLast() {
        if (isEmpty()) {
            return null;
        }
        Node<T> l = last;
        T result = l.item;
        last = last.prev;
        if (last == null) {
            first = null;
        } else {
            last.next = null;
            l.prev = null;
            l.item = null;
        }
        size--;
        return result;
    }

    @Override
    public void clear() {
        if (isEmpty()) {
            return;
        }
        for (Node<T> node = first; node != null; ) {
            Node<T> nextNode = node.next;
            node.item = null;
            node.next = null;
            node.prev = null;
            node = nextNode;
        }
        size = 0;
        first = null;
        last = null;
    }

    @Override
    public T get(int index) {
        checkElementIndex(index);
        return getNode(index).item;
    }

    public T getFirst() {
        final Node<T> f = first;
        if (f == null)
            throw new NoSuchElementException();
        return f.item;
    }

    public T getLast() {
        final Node<T> l = last;
        if (l == null)
            throw new NoSuchElementException();
        return l.item;
    }

    private Node<T> getNode(int index) {
        Node<T> node;
        if (index < size >> 2) {
            node = first;
            for (int i = 0; i < index; i++) {
                node = node.next;
            }
        } else {
            node = last;
            for (int i = size - 1; i > index; i--) {
                node = node.prev;
            }
        }
        return node;
    }

    @Override
    public T set(int index, T element) {
        checkElementIndex(index);
        Node<T> oldNode = getNode(index);
        T oldVal = oldNode.item;
        oldNode.item = element;
        return oldVal;
    }

    @Override
    public T removeByIndex(int index) {
        checkElementIndex(index);
        if (index == 0) {
            return removeFirst();
        } else if (index == size - 1) {
            return removeLast();
        } else {
            Node<T> node = getNode(index);
            T result = node.item;
            node.prev.next = node.next;
            node.next.prev = node.prev;
            node.next = null;
            node.prev = null;
            node.item = null;
            size--;
            return result;
        }
    }

    @Override
    public int indexOf(T o) {
        int index = 0;
        if (o == null) {
            for (Node<T> node = first; node != null; node = node.next) {
                if (node.item == null) {
                    return index;
                }
                index++;
            }
        } else {
            for (Node<T> node = first; node != null; node = node.next) {
                if (node.item.equals(o)) {
                    return index;
                }
                index++;
            }
        }
        return -1;
    }

    private void checkElementIndex(int index) {
        if (!isElementIndex(index))
            throw new IndexOutOfBoundsException("index is out of bounds");
    }

    private boolean isElementIndex(int index) {
        return index >= 0 && index < size;
    }

    @Override
    public RIterator<T> iterator() {
        return new DLinkedListIterator();
    }

    private class DLinkedListIterator implements RIterator<T> {

        private int index;
        private Node<T> node;

        public DLinkedListIterator() {
            node = first;
        }

        @Override
        public boolean hasNext() {
            return index < size;
        }

        @Override
        public T next() {
            T result = node.item;
            node = node.next;
            index++;
            return result;
        }
    }
}

测试代码就不贴出来，在 github 上自己看下吧！有问题或者需要优化的地方可以讨论下！

代码地址

Java 代码

C 代码