【链表的说明、方法---顺序表与链表的区别】

---

前言

什么是链表

含义：链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的 。

图形解释：
逻辑上是连续的，但物理上看起来不连续
这个图形也叫单向不带头非循环

链表的结构

非常多样，有8种结构

重点掌握下面两种：

无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。

无头双向链表：在Java的集合框架库中LinkedList底层实现就是无头双向循环链表。

带头和不带头的区别

链表的实现（方法）

定义接口

public interface ILIst {
    // 1、无头单向非循环链表实现
        //头插法
        void addFirst(int data);
        //尾插法
        void addLast(int data);
        //任意位置插入,第一个数据节点为0号下标
        void addIndex(int index,int data);
        //查找是否包含关键字key是否在单链表当中
        public boolean contains(int key);
        //删除第一次出现关键字为key的节点
        void remove(int key);
        //删除所有值为key的节点
        void removeAllKey(int key);
        //得到单链表的长度
        int size();
        void clear();
        void display();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

遍历链表

1.怎么从一个节点走到下一个节点
head = head.next

2.怎么判断所有节点遍历完了
当head = null 循环结束

//            while(head != null){
//                System.out.print(head.val+" ");
//                head = head.next;
//            }
 //这个方法遍历完head=null,会导致链表空了，找不到第一个节点在哪了
//所以应该把head赋值给一个数，让它去遍历，相当于head的分身，分身消失了，主体head还在

        ListNode cur = this.head;
        //进入循环条件为链表不为空
        //也就是说当head为空时，循环结束
        while(cur != null){
            System.out.print(cur.val+" ");
            cur =cur.next;
        }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

头插法

    //头插法
    //时间复杂度O（1）
    @Override
    public void addFirst(int data) {
            //先实例化一个节点
        ListNode node = new ListNode(data);
        //如果链表没有节点，那么插入的这个节点就是第一个节点
        //所以head = node
        if (this.head ==null){
            this.head = node;
        }else {
            node.next = this.head;
            this.head = node;

        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

尾插法

    //尾插法:在最后创建一个节点
    //时间复杂度O（N）
    @Override
    public void addLast(int data) {
            //创建一个新节点
        ListNode node = new ListNode(data);
        ListNode cur = this.head;
        //当链表为空时，此案件的新节点就是第一个节点
        if (this.head == null){
            this.head = node;
        }else {
            //让cur遍历完走到cur.next为空时，才找到了最后一个节点
            //意思就是走出了while循环，就说明cur走到了最后一个节点上
            while (cur.next != null){
                cur = cur.next;
            }
            cur.next = node;
            node.next =null;
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

任意位置插入一个节点

    //让cur去到index-1位置
    private ListNode searchPrev(int index){
            ListNode cur = this.head;
            int count =0;
            while(count != index-1){
                cur = cur.next;
                count++;
            }
            //循环走完, cur已经走到index-1得位置了
            return cur;
    }

    //任意位置插一个节点
    @Override
    public void addIndex(int index, int data) {
            ListNode node = new ListNode(data);
            //检查index得合法性
        if (index < 0 || index > size()){
            //抛自定义异常
            return ;
        }
        //如果index=0 头插法
        if (index == 0){
            addFirst(data);
            return;
        }
        //如果index=size,尾插法
        if (index == size()){
            addLast(data);
            return;
        }
        
        ListNode cur =  searchPrev(index);//调用cur走到index-1的方法
        node.next = cur.next;
        cur.next = node;
    }
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

链表中是否包含某个数字

    //链表是否包含某个数字
    @Override
    public boolean contains(int key) {
            ListNode cur = this.head;
            while(cur != null){
                if (cur.val == key){
                    return true;
                }
                cur = cur.next;
            }
        return false;
    }

    @Override
    public void remove(int key) {

    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

删除链表某个节点

    //让cur走到要删除的节点的前一个节点
    private ListNode findPrev(int key){
        ListNode cur = this.head;
        //判断条件是cur不能超过倒数二个节点
    while(cur.next != null ){
        if (cur.next.val == key){
                return cur;
        }
        cur = cur.next;
    }
        return null;

    }
    @Override
    public void remove(int key) {
            //如果链表为空,无法删除
        if (this.head == null){
            return ;
        }

       //如果要删除第一个节点
       if (this.head.val ==key){
            this.head = this.head.next;
            return;
       }
        //判断前驱
        ListNode cur = findPrev(key);
        //判断返回值是否为空
        if (cur == null){
            System.out.println("没有你要删除的数字！");
            return ;
        }
        //删除
        ListNode del = cur.next;
        cur.next = del.next;
    }


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

删除链表中所有关键字key

    //删除链表中所有关键字key
    @Override
    public void removeAllKey(int key) {
            if (this.head == null){
                return;
            }

        ListNode prev = this.head;
        ListNode cur = this.head.next;
            while(cur != null){
                if (cur.val == key){
                    prev.next = cur.next;
                    cur = cur.next;
                }else{
                    prev = cur;
                    cur = cur.next;
                }
            }

            if (this.head.val == key){
                this.head = head.next;
            }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

清空链表所有节点

    public void clear() {
      ListNode cur = this.head;
      while(cur != null){
      ListNode curNext  = cur.next;
      cur.next =null;
      cur = curNext;
      }
      this.head = null;
    }
1
2
3
4
5
6
7
8
9

ArrayList 和 LinkedList的区别

总结

以上就是关于链表的详细知识。