集册 Java实例教程 双链接列表

双链接列表

欢马劈雪     最近更新时间:2020-01-02 10:19:05

497
双链接列表

package com.company.stucts.list;
//N o  w  J a v a . c o m - 时  代  Java 提 供

import java.util.Iterator;


@SuppressWarnings({ "Duplicates", "WeakerAccess" })

public class DoublyLinkedList<T> implements Iterable<T> {

    private Node<T> tail, head;

    private int size;


    public void addBack(T value) {

        if (tail == null) {

            head = tail = new Node<T>(value);

            size++;

            return;

        }


        Node<T> newNode = new Node<>(value);

        tail.next = newNode;

        newNode.prev = tail;

        tail = newNode;
//时 代 J a v a - N o w J a v a . c o m

        size++;

    }


    public void addFront(T value) {

        if (tail == null) {

            head = tail = new Node<T>(value);

            return;

        }


        Node<T> newNode = new Node<T>(value);

        newNode.next = head;

        head.prev = newNode;

        head = newNode;

    }


    public void removeFront() {

        if (size == 0) {

            throw new IllegalStateException("List is empty");

        }


        Node<T> newHead = head.next;

        newHead.prev = null;

        head.next = null;

        head = newHead;

    }


    public void removeBack() {

        if (size == 0) {

            throw new IllegalStateException("List is empty");

        }


        Node<T> newTail = tail.prev;

        newTail.next = null;

        tail.prev = null;

        tail = newTail;

    }


    public T popFront() {

        if (size == 0) {

            throw new IllegalStateException("List is empty");

        }


        Node<T> newHead = head.next;

        newHead.prev = null;

        head.next = null;

        T value = head.value;

        head = newHead;

        return value;

    }


    public void reverseList() {

        Node<T> node = tail;

        while (node != null) {

            swapLink(node);

            node = node.next;

        }


        Node<T> tmp = head;

        head = tail;

        tail = tmp;

    }


    public boolean isEmpty() {

        return size == 0;

    }


    private void swapLink(Node<T> node) {

        Node<T> tmp = node.next;

        node.next = node.prev;

        node.prev = tmp;

    }


    public Iterable<T> reversedIterator() {

        return new Iterable<T>() {

            @Override

            public Iterator<T> iterator() {

                return new Iterator<T>() {

                    private Node<T> node = tail;


                    @Override

                    public boolean hasNext() {

                        return node != null;

                    }


                    @Override

                    public T next() {

                        T value = node.value;

                        node = node.prev;

                        return value;

                    }

                };

            }

        };

    }


    @Override

    public Iterator<T> iterator() {

        return new Iterator<T>() {

            private Node<T> node = head;


            @Override

            public boolean hasNext() {

                return node != null;

            }


            @Override

            public T next() {

                T value = node.value;

                node = node.next;

                return value;

            }

        };

    }


    private static class Node<T> {

        private T value;

        private Node<T> next;

        private Node<T> prev;


        Node(T value) {

            this.value = value;

        }

    }


    @Override

    public String toString() {

        
展开阅读全文