LinkedList链表

LinkedList 的全面说明

• LinkList底层实现了双向链表和双端队列特点
• 可以添加任意元素（元素可以重复），包括null
• 线程不安全，没有实现同步

LinkedList 的底层操作机制

• LinkedList底层维护了一个双向链表
• LinkList中维护了两个属性first和last分别指向 首节点和尾结点
• 每个节点（Node对象），里面有维护了prev、next、item三个属性
  prev：指向前一个
  next：指向后一个
  最终实现双向链表
• ListedList的元素的添加和删除，不是通过数组完成的，相对来说效率高
• 模拟一个简单的双向链表-代码：

public class LinkedList_ {
    public static void main(String[] args) {
        //模拟一个简单的双向链表
        //1，创建Node对象
        Node jack = new Node("jack");
        Node tom = new Node("tom");
        Node zl = new Node("zl");
        //2，连接3个结点，形成双向链表
        //      jack -> tom -> zl
        jack.next = tom;
        tom.next = zl;
        //      zl -> tom -> jack
        zl.pre = tom;
        tom.pre = jack;
        //3，指定双向链表的头节点-jack；尾结点-zl
        Node first = jack;
        Node last = zl;
        //4，从头到尾遍历
        System.out.println("=======从头到尾遍历===========");
        while (true){
            if (first == null){break;}
            System.out.println(first);
            first = first.next;
        }
        //5，从尾到头遍历
        System.out.println("=====从尾到头遍历======");
        while (true){
            if (last==null){break;}
            System.out.println(last);
            last=last.pre;
        }
        //6，添加对象/数据
        System.out.println("======添加数据后======");
        Node add1 = new Node("add1");
        //添加到jack 和 tom 中间
        add1.next = tom;
        add1.pre=jack;
        tom.pre=add1;
        jack.next=add1;
        first = jack;
        while (true){
            if (first == null){break;}
            System.out.println(first);
            first = first.next;
        }
        System.out.println("=======添加数组后从后往前遍历=========");
        last=zl;
        while (true){
            if (last==null){break;}
            System.out.println(last);
            last=last.pre;
        }
    }
}

//定义一个Node类，Node对象，表示双向链表的一个节点
class Node {
    public Object item;//真正存放数据
    public Node next;//指向后一个结点
    public Node pre;//指向前一个节点

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

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

结果

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);
        System.out.println("linkedList=" + linkedList);

        //删除节点
//        linkedList.remove(); // 这里默认删除的是第一个结点
        linkedList.remove(1);
        System.out.println("删除后linkedList="+ linkedList);

        //修改某个节点  将index=1位置的对象修改为999
        linkedList.set(1,999);
        System.out.println("修改后的linkedList"+linkedList);

        //得到某个节点
        System.out.println("得到下标为1的对象"+linkedList.get(1));

        //遍历方式，因为LinkedList 是实现了 List接口，因此遍历方式为List的三个遍历方式
        System.out.println("===LinkeList 遍历迭代器====");
        Iterator iterator = linkedList.iterator();
        while (iterator.hasNext()) {
            Object next = iterator.next();
            System.out.println(next);
        }

        System.out.println("===LinkeList 遍历增强 for====");
        for (Object o:linkedList){
            System.out.println(o);
        }

        System.out.println("===LinkeList 遍历普通 for====");
        for (int i = 0; i < linkedList.size(); i++) {
            System.out.println(linkedList.get(i));
        }
    }

}

结果

ArrayList 和 LinkedList 的比较

LinkedList的增删改查

• 增：1，创建结点对象；2，通过链表追加前后连接；3，遍历
• 删： linkedList.remove(); // 这里默认删除的是第一个结点
• 改：linkedList.set(1,999); 将index=1位置的对象修改为999
• 查：三种方式遍历：1，遍历迭代器；2，遍历增强for；3，遍历普通for

ArrayList的增删改查

• 增：扩容，创建新数组，复制，比较麻烦
• 删：创建新数组，复制，比较麻烦
• 改：数组名[下标] 直接修改
• 查：for循环遍历