Java集合03

8.LinkedList

1）linkedList底层实现了**双向链表**和**双端队列**的特点

2）可以添加任意元素（元素可以重复），包括null

3）线程不安全，没有实现同步

• LinkedList的底层操作机制
• LinkedList底层维护了一个双向链表
• LinkedList中维护了两个属性first和last，分别指向首节点和尾节点
• 每个节点（Node对象）里面又维护了prev、next、item三个属性，其中通过prev指向前一个节点，通过next指向后一个节点，最终实现双向链表。
• 所以LinkedList的元素的**添加和删除**不是通过数组完成的，相对来说效率较高

8.1双向链表

例子：实现简单的双向链表

package li.collections.list.linkedlist;


public class LinkedListTest {

    public static void main(String[] args) {
        Node jack = new Node("jack");
        Node tom = new Node("tom");
        Node marry = new Node("marry");

        //连接节点，形成双向链表
        //jack-->tom-->marry
        jack.next = tom;
        tom.pre = jack;
        tom.next = marry;
        marry.pre = tom;

        Node first = jack;//让头节点指向Jack
        Node last = marry;//尾节点指向marry

        //从头到尾遍历
        while (true) {
            if (first == null) {
                break;
            }
            System.out.println(first);
            first = first.next;
        }

        System.out.println("==========");

        //从尾到头遍历
        while (true) {
            if (last == null) {
                break;
            }
            System.out.println(last);
            last = last.pre;
        }


    }
}

//定义一个Node对象，表示节点
class Node {
    public Object item;//存放数据
    public Node next;//指针指向下一个节点
    public Node pre;//指针指向上一个节点

    public Node(Object name) {
        this.item = name;
    }

    @Override
    public String toString() {
        return "Node item=" + item;
    }
}

例子2：双向链表节点的增加和删除

package li.collections.list.linkedlist;


public class LinkedListTest {

    public static void main(String[] args) {
        Node jack = new Node("jack");
        Node tom = new Node("tom");
        Node marry = new Node("marry");

        //连接节点，形成双向链表
        //jack-->tom-->marry
        jack.next = tom;
        tom.pre = jack;
        tom.next = marry;
        marry.pre = tom;

        Node last = marry;//尾节点指向marry


        //链表添加数据
        //要求在tom和marry之间插入一个对象json
        Node json = new Node("json");

        //指针先连后删
        json.pre = tom;
        json.next = marry;
        marry.pre = json;
        tom.next = json;

        Node first = jack;//让头节点再次指向Jack

        //从头到尾遍历
        while (true) {
            if (first == null) {
                break;
            }
            System.out.println(first);
            first = first.next;
        }

    }
}

//定义一个Node对象，表示节点
class Node {
    public Object item;//存放数据
    public Node next;//指针指向下一个节点
    public Node pre;//指针指向上一个节点

    public Node(Object name) {
        this.item = name;
    }

    @Override
    public String toString() {
        return "Node item=" + item;
    }
}

8.2LinkedList底层结构

常用方法：

例子1：LinkedList双向链表增加数据

package li.collections.list.linkedlist;

import java.util.LinkedList;

public class LinkedListCRUD {
    @SuppressWarnings("all")
    public static void main(String[] args) {
        LinkedList linkedList = new LinkedList();

        linkedList.add(1);
        linkedList.add(2);

        System.out.println("linkedList="+linkedList);


    }
}

1. 在执行LinkedList linkedList = new LinkedList();时，LinkedList底层创建了一个空的列表

1. 执行linkedList.add(1);时，首先进行自动装箱（略），然后调用底层的add（）方法，add（）又调用linkLast（）方法。

linkLst（）方法将新的节点加到双向链表的最后：

首先创建一个node类型的常量 l ，首先将last的地址赋给l，因为刚开始没有数据，last指向null，因此l同样也指向null。

再创建一个新的节点newNode，将add（1）传入的参数赋给newNode，newNode的pre指向l，即指向null，newNode的next也指向null。

然后将last指向newNode

第一次的l指向了null，因此执行first也指向新结点newNode语句

最后是链表长度加1，修改次数modCount加1

所以，第一个节点的时候情况如图：

---

linkedList.add(2);执行第二次添加操作时，重复上述操作，最后来到linkLast（）方法。

1. 此时last指向的是第一个节点，执行final Node<E> l = last;，则 l 也指向第一个节点。

2. 再新建一个节点，将 l 设置为新结点的pre，即将新结点的前置节点设置为了第一个节点，将新结点的next设置为空。final Node<E> newNode = new Node<>(l, e, null);

3. 将last指向新结点
4. 这里 l不再指向null，因此执行l.next=newNode;语句，因为l这时指向第一个节点，所以执行语句之后第一个节点的next将会指向newNode

例子2：双向链表删除数据

package li.collections.list.linkedlist;

import java.util.LinkedList;

public class LinkedListCRUD {
    @SuppressWarnings("all")
    public static void main(String[] args) {
        LinkedList linkedList = new LinkedList();

        linkedList.add(1);
        linkedList.add(2);
        linkedList.add(3);

        linkedList.remove();//这里默认删除第一个节点
        System.out.println("linkedList="+linkedList);//linkedList=[2, 3]


    }
}

分析unlinkFirst（）方法：将f指向的双向链表中的第一个节点删除

1. 首先在removeFirst（）方法中将 f 指向第一个节点：final Node<E> f = first;

2. 然后取出第一个节点的值item：final E element = f.item;

3. 然后将第一个节点next存储的地址赋给常量next，即将next指向第二个节点：final Node<E> next = f.next;

4. 然后将第一个节点的值置空，以及将第一个节点指向的地址置空，这样第一节点指向第二节点的next就断开了：f.item = null;

​ f.next = null; // help GC

1. 然后将next的地址赋给first，此时的next已经指向了第二个节点，所以first也指向第二个节点：first = next;
2. 然后判断next是否为空，即判断删除的节点时候为最后一个节点，如果是，则将last置空；若否则将next指向节点的pre置空，也就是将第二个节点指向第一节点的指针断开。

if (next == null)
    last = null;
else
    next.prev = null;

1. 而后链表长度-1，链表操作次数+1

2. 最后返回删除数据的内容

例子3：其他常用方法

package li.collections.list.linkedlist;

import java.util.Iterator;
import java.util.LinkedList;

public class LinkedListCRUD {
    @SuppressWarnings("all")
    public static void main(String[] args) {
        LinkedList linkedList = new LinkedList();

        linkedList.add(1);
        linkedList.add(2);
        linkedList.add(3);

        //修改某个节点对象
        linkedList.set(1,999);//public E set(int index, E element)
        System.out.println("linkedList="+linkedList);//linkedList=[1, 999, 3]

        //得到某个节点对象
        System.out.println(linkedList.get(1));//得到第二个节点对象 999

        //遍历:因为LinkedList实现了List接口，所以LinkedList也可以使用增强for循环和迭代器
        // 1.增强for循环
        for (Object o:linkedList) {
            System.out.println(o);

        }

        //2.迭代器
        Iterator iterator = linkedList.iterator();
        while (iterator.hasNext()) {
            Object next =  iterator.next();
            System.out.println(next);
        }

        //3.普通for循环
        for (int i = 0; i < linkedList.size(); i++) {
            System.out.println(linkedList.get(i));
        }


    }
}

8.3ArrayList和LinkedList的比较

	底层结构	增删的效率	改查的效率
ArrayList	可变数组	较低：数组扩容	较高
LinkedList	双向链表	较高：通过链表追加	较低

如任选择ArrayList和LinkedList：

1. 如果我们改查比较多，选择ArrayList
2. 如果增删比较多，选择LinkedList
3. 一般来说，在程序中百分之80到90都是查询，因此大部分情况下会选择ArrayList
4. 在一个项目中，根据业务灵活查询，也可以两个集合一起用。一个模块使用ArrayList，另一个模块使用LinkedList