程序员最近都爱上了这个网站  程序员们快来瞅瞅吧!  it98k网:it98k.com

本站消息

站长简介/公众号

  出租广告位,需要合作请联系站长


+关注
已关注

分类  

暂无分类

标签  

暂无标签

日期归档  

2022-02(37)

2022-03(16)

2022-04(11)

2022-05(14)

2022-06(31)

Java基础之:List——LinkedList

发布于2020-12-29 07:16     阅读(621)     评论(0)     点赞(9)     收藏(1)


Java基础之:List——LinkedList

 

 

LinkedList简单介绍

LinkedList实现了双向链表(数据结构)和双端队列特点。

实现了List接口,可以添加任意元素(即可以重复和null),线程不安全。

LinkedList底层实现分析

  1. LinkedList底层维护了一个双向链表

  2. LinkedList中维护了两个属性first和last,分别指向首节点和尾节点

  3. 每个节点(数据结构中将节点都称作Node对象),里面又维护了prev、next、item三个属性。其中prev指向前一个Node,next指向后一个Node,最终实现双向链表。

  4. 所以LinkedList的元素添加与删除不是通过数组完成的,效率较高。

模拟最简单的双向链表:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
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常用方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
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内部类源码

1
2
3
4
5
6
7
8
9
10
11
  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:

  1. 如果我们改查的操作多,选择ArrayList

  2. 如果我们增删的操作多,选择LinkedList

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

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

 

 



所属网站分类: 技术文章 > 博客

作者:javajava我最强

链接:http://www.javaheidong.com/blog/article/45597/bb25dc574c00322d7ec9/

来源:java黑洞网

任何形式的转载都请注明出处,如有侵权 一经发现 必将追究其法律责任

9 0
收藏该文
已收藏

评论内容:(最多支持255个字符)