Java基础之：List——LinkedList
LinkedList简单介绍
LinkedList实现了双向链表(数据结构)和双端队列特点。
实现了List接口，可以添加任意元素(即可以重复和null)，线程不安全。
LinkedList底层实现分析
LinkedList底层维护了一个双向链表
LinkedList中维护了两个属性first和last，分别指向首节点和尾节点
每个节点(数据结构中将节点都称作Node对象)，里面又维护了prev、next、item三个属性。其中prev指向前一个Node，next指向后一个Node，最终实现双向链表。
所以LinkedList的元素添加与删除不是通过数组完成的，效率较高。
模拟最简单的双向链表：
package class_LinkedList;public class ClassTest01_DoubleLinkedList { public static void main(String[] args) { Node first = null;//首先定义一个first节点，作为标记位置存在 //当添加一个节点时，让first节点指向此节点 Node node1 = new Node(first, null, "小范"); first = node1; //添加第二个节点，在构造时，让第二个节点的prev属性指向前一个节点node1 Node node2 = new Node(node1, null, "小黄"); node1.next = node2; //让node1的next指向node2，实现双向连接 //添加第三个节点 Node node3 = new Node(node2, null, "小雨"); node2.next = node3; //结尾 ，使用last节点，让last节点指向node3，因为node3的next为null代表链表结束 Node last = node3; //链表遍历，通常都使用一个临时temp节点来用于遍历链表，不要使用first！ Node temp = first; //链表从前向后遍历 System.out.println("==========从前向后============"); while(true) { System.out.println(temp); if(temp.next == null) { //last节点的next属性为null break; } temp = temp.next; //将temp向后移 } //链表从后向前遍历 System.out.println("==========从后向前============"); temp = last; while(true) { System.out.println(temp); if(temp.prev == null) { //first节点的prev属性为null break; } temp = temp.prev; //将temp向前移 } //添加节点，让需要添加位置的前后节点分别指向要添加的节点即可。 //创建需要添加的节点，让其prev属性指向要添加位置的前一个节点，next属性指向要添加位置的后一个节点 Node add = new Node(node1,node2,"add"); //在第一个和第二个节点中间插入一个节点 //将node1的next指向add，node2的prev指向add，完成连接，此时node1与node2之间的连接自然就断开了 node1.next = add; node2.prev = add; //再次遍历检查是否添加成功 System.out.println("==========添加后==========="); temp = first; while(true) { System.out.println(temp); if(temp.next == null) { //last节点的next属性为null break; } temp = temp.next; //将temp向后移 } }}class Node{ //说明 这里为了方便演示案例，没有进行封装，实际开发中需要封装 Node prev; //指向前一个节点 Node next; //指向后一个节点 String name; //每个节点的自有属性 public Node(Node prev, Node next, String name) { this.prev = prev; this.next = next; this.name = name; } @Override public String toString() { return "Node [name=" + name + "]"; }}
程序输出：
==========从前向后============
Node [name=小范]
Node [name=小黄]
Node [name=小雨]
==========从后向前============
Node [name=小雨]
Node [name=小黄]
Node [name=小范]
==========添加后===========
Node [name=小范]
Node [name=add]
Node [name=小黄]
Node [name=小雨]
LinkedList常用方法
package class_LinkedList;import java.util.LinkedList;public class ClassTest02_LinkedListMethods { @SuppressWarnings({ "rawtypes", "unchecked" }) public static void main(String[] args) { LinkedList linkedList = new LinkedList(); // 添加 for (int i = 0; i < 2; i++) { linkedList.add("AAA" + i); } String kk = "yyy"; linkedList.add(kk); linkedList.add(2, kk); // 遍历 for (Object object : linkedList) { System.out.println(object); } // 删除 // linkedList.remove(0); // linkedList.remove(kk); System.out.println("================="); //替换 linkedList.set(0, "川农"); for (Object object : linkedList) { System.out.println(object); } System.out.println("================="); //查找，也可以使用下标进行访问 Object object = linkedList.get(0); System.out.println("object=" + object); //LinkedList特有方法，获取首尾节点 System.out.println(linkedList.getFirst()); System.out.println(linkedList.getLast()); }}
添加节点源码分析
默认添加：
带下标位置的添加：
Node内部类源码
private static class Node<E> { E item; Node<E> next; Node<E> prev; Node(Node<E> prev, E element, Node<E> next) { this.item = element; this.next = next; this.prev = prev; } }
Node内部类维护了next与prev属性。
LinkedList与ArrayList对比
如何选择ArrayList和LinkedList：
如果我们改查的操作多，选择ArrayList
如果我们增删的操作多，选择LinkedList
一般来说，在程序中，80%-90%都是查询，因此大部分情况下会选择ArrayList
在一个项目中，根据业务灵活选择，也可能这样，一个模块使用的是ArrayList,另外一个模块是LinkedList.
赞 (0)