LinkedList
                    使用场景:
                    如果仅在两端操作数据，用LinkedList
                    数据量较小时（100以内），频繁增删数据用LinkedList
                    双向链表：两端效率高，越往中间效率越低

---

创新互联一直通过网站建设和网站营销帮助企业获得更多客户资源。 以"深度挖掘，量身打造，注重实效"的一站式服务，以成都网站设计、成都网站建设、移动互联产品、全网整合营销推广服务为核心业务。十多年网站制作的经验，使用新网站建设技术，全新开发出的标准网站，不但价格便宜而且实用、灵活，特别适合中小公司网站制作。网站管理系统简单易用，维护方便，您可以完全操作网站资料，是中小公司快速网站建设的选择。

---

package 集合.list.LinkedList;

public class MyLinkedList {
    //默认长度为0
    private int size = 0;
    Node head = null;
    Node tail = null;

    public MyLinkedList() {
    }

    //添加元素的方法
    public void add(Object obj) {
        //创建Node
        Node node = new Node(obj, null, null);
        //先判断之前的尾部节点
        if (size == 0) {
            this.head = node;
        } else {
            Node temp;
            temp = this.tail;
            temp.next = node;
            node.prev = temp;
        }
        this.tail = node;
        size++;
    }

    //插入元素
    public void add(int index, Object obj) {
        //先判断索引是否合法
        if (index > size || index < 0) {
            throw new IndexOutOfBoundsException();
        }
        //判断插入位置
        if (index == size) {
            this.add(obj);
            return;
        }
        //创建Node
        Node node = new Node(obj, null, null);
        Node temp = null;
        //如果插入是头部
        if (index == 0) {
            temp = this.head;
            this.head = node;
            node.next = temp;
            temp.prev = node;
        } else {
            // 如果插入中间位置
            Node insertNode = indexOf(index);
            Node prev = insertNode.prev;

            node.prev = prev;
            node.next = insertNode;

            prev.next = node;
            insertNode.prev = node;
        }
        size++;
    }

    //删除指定索引元素
    public void remove(int index) {

        Node n;
        if (index == 0) {
            n = head.next;
            head = n;
            n.prev = null;
        } else if (index == size - 1) {
            n = tail.prev;
            tail = n;
            n.next = null;
        } else {
            Node node = indexOf(index);
            Node prev = node.prev;
            Node next = node.next;
            prev.next = next;
            next.prev = prev;
            // node.prev = null;
            //node.next = null;
        }
        size--;
    }

    //删除第一个出现的元素
    public void remove(Object obj) {
        int index = indexOf(obj);
        if (index != -1) {
            remove(index);
        }
    }

    //查找元素返回索引
    public int indexOf(Object obj) {
        //获取头节点
        Node node = head;
        for (int i = 0; i < size; i++) {
            if (node.value == obj || node.value != null && node.value.equals(obj)) {
                return i;
            }
            node = node.next;
        }
        return -1;
    }

    //查找指定索引的元素
    public Node indexOf(int index) {
        if (index == 0) {
            return head;
        }
        if (index == size - 1) {
            return tail;
        }
        Node n;
        if (index <= size / 2) {
            //前一半
            n = head;
            for (int i = 1; i < index; i++) {
                n = n.next;
            }
        } else {
            n = tail;
            for (int i = size - 2; i >= index; i--) {
                n = n.prev;
            }
        }
        return n;
    }

    //判断是否包含元素
    public boolean cotains(Object obj) {
        return indexOf(obj) != -1;
    }

    //获取长度
    public int getSize() {
        return size;
    }

    //判断是否为空
    public boolean isEmpty() {
        return size == 0;
    }

    //清空链表
    public void clear() {
        //设置头尾节点为null,size=0
        this.tail = null;
        this.head = null;
        size = 0;
    }

    //通过索引修改数据
    public void set(int index, Object obj) {
        //先判断索引是否合法
        if (index > size || index < 0) {
            throw new IndexOutOfBoundsException();
        }
        indexOf(index).value = obj;
    }

    //获取子链表
    public MyLinkedList sublist(int fromIndex, int toIndex) {
        //判断越界
        //先判断索引是否合法
        if (toIndex > size || fromIndex < 0) {
            throw new IndexOutOfBoundsException();
        }
        MyLinkedList sublist = new MyLinkedList();
        //先获取fromIndex处的节点
        Node node = indexOf(fromIndex);
        for (int i = fromIndex; i < toIndex; i++) {
            //将对于节点处的值加入到子链表中
            sublist.add(node.value);
            //每次循环需要改变节点
            node = node.next;
        }
        return sublist;
    }

    //重写toString
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("[");
        //获取节点
        Node node = head;
        for (int i = 0; i < size; i++) {
            if (i != size - 1) {
                sb.append(node.value).append(",");
            } else {
                sb.append(node.value);
            }
            node = node.next;
        }
        sb.append("]");
        return sb.toString();
    }

    //定义节点内部静态类
    private static class Node {
        //节点的数据
        Object value;
        //节点的下一个地址
        Node next;
        //上一个地址
        Node prev;

        Node(Object value, Node prev, Node next) {
            this.value = value;
            this.next = next;
            this.prev = prev;
        }
    }
}

网站栏目：JAVA自己实现LinkedList
文章路径：http://myzitong.com/article/gjiecj.html