数据结构学习笔记-链表中的双向链表（JAVA）

概念：
双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，
分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，
都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。
实现方式：构造一个常驻内存的头节点引用，然后头节点的上一个节点是最后一个节点，最后
一个节点的下一个是头节点。其他的每个节点都有上下节点的引用。最少有一个头节点
操作：构造链表，销毁链表，计算元素个数，返回链表中指定链表中元素的值，插入元素，删除元素
代码:
package com.alg.link;
import java.util.Iterator;
//双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，
//分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，
//都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。
//链表的操作有：构造链表，销毁链表，计算元素个数，返回链表中指定链表中元素的值，插入元素，删除元素

public class DoubleWayLinkedList<T> extends BaseLinkedList<T>
{
    transient Link<T> voidLink;
    public DoubleWayLinkedList()
    {
        voidLink = new Link<T>(null, null, null);
        voidLink.previous = voidLink;
        voidLink.next = voidLink;
    }
    // 向尾部添加
    @Override
    public void add(T object)
    {
        Link<T> oldLast = voidLink.previous;
        // 末尾的上一个是最后一下，下一个是第一个
        Link<T> newLink = new Link<T>(object, oldLast, voidLink);
        voidLink.previous = newLink;
        oldLast.next = newLink;
        modCount++;
        size++;
    }
    @Override
    public void clear()
    {
        if (size > 0)
        {
            size = 0;
            voidLink.next = voidLink;
            voidLink.previous = voidLink;
            modCount++;
        }
    }
    @Override
    public T get(int location)
    {
        if (0 <= location && location < size)
        {
            Link<T> link = voidLink;
            if (location < (size / 2))
            {
                for (int i = 0; i <= location; i++)
                {
                    link = link.next;
                }
            }
            else
            {
                for (int i = size; i > location; i--)
                {
                    link = link.previous;
                }
            }
            return link.data;
        }
        return null;
    }
    // 移除某个元素
    @Override
    public T remove(int location)
    {
        if (0 <= location && location < size)
        {
            Link<T> link = voidLink;
            if (location < (size / 2))
            {
                for (int i = 0; i <= location; i++)
                {
                    link = link.next;
                }
            }
            else
            {
                for (int i = size; i > location; i--)
                {
                    link = link.previous;
                }
            }
            Link<T> previous = link.previous;
            Link<T> next = link.next;
            previous.next = next;
            next.previous = previous;
            size--;
            modCount++;
            return link.data;
        }
        return null;
    }
    // 可以加入空的数据,所以有object为null的移除，而且移的是第一个数据为null的
    @Override
    public boolean remove(Object object)
    {
        Link<T> link = voidLink.next;
        if (object != null)
        {
            while (link != voidLink && !object.equals(link.data))
            {
                link = link.next;
            }
        }
        else
        {// 如果data为null,则碰到了第一个空数据
            while (link != voidLink && link.data != null)
            {
                link = link.next;
            }
        }
        if (link == voidLink)
        {
            return false;
        }
        Link<T> next = link.next;
        Link<T> previous = link.previous;
        previous.next = next;
        next.previous = previous;
        size--;
        modCount++;
        return true;
    }
    @Override
    public int size()
    {
        return size;
    }
    public Iterator<T> iterator()
    {
        return new SimpleIterator();
    }
}