[Java教程]Java基础之：List——LinkedList

0 2020-12-26 11:47:15

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 item; Node next; Node prev;​ Node(Node prev, E element, Node next) { this.item = element; this.next = next; this.prev = prev; } }

Node内部类维护了next与prev属性。

LinkedList与ArrayList对比

如何选择ArrayList和LinkedList：如果我们改查的操作多，选择ArrayList

如果我们增删的操作多，选择LinkedList

一般来说，在程序中，80%-90%都是查询，因此大部分情况下会选择ArrayList

在一个项目中，根据业务灵活选择，也可能这样，一个模块使用的是ArrayList,另外一个模块是LinkedList.

本文网址：http://www.shaoqun.com/a/504066.html

*特别声明：以上内容来自于网络收集，著作权属原作者所有，如有侵权，请联系我们：admin@shaoqun.com。

Java

0