链表（一）——无头单向非循环链表实现_无头链表 csdn

一、初始链表

• 链表属于线性结构，包含一个元素序列，序列中的每一个元素都可以引用序列中下一个元素。
• 链表在物理空间上是非连续的，每一个元素之间存在间隙，在逻辑上，是连续的，每一个序列中的元素与下一个元素形成链式结构，跟轨道上的火车一样，整体形成一个有序序列。
• 链表通过一个个结点组成，每一个结点里包括数据域和储存下一个结点地址的next，有时候存在虚拟结点，就是不存在数据域，只有next，它的作用是将头部和其他位置相统一，方便后续的添加、插入、删除等操作。
  
• 现实中的结点一般都是在堆上申请空间

顺序表与链表的区别

• 顺序表在物理空间上是连续的，其底层逻辑由数据搭建，链表序列的每一个元素是通过结点上的next来实现逻辑上的连续
• 链表不存在扩容问题，顺序表的数组是指定的大小，当指定的大小已经满了，就会扩大容量，系统一般会以1.5倍扩容，如果没有充分利用就会浪费空间，造成内存碎片
• 链表插入和删除，时间复杂度与顺序表一样，总体都是O(n)级别，但是链表的效率比顺序表快很多，因为链表插入和删除不用挪数据，只用读数据，而顺序表插入一个数据和删除一个数据，后续序列的元素都需要跟着向前或者向后移动。不过尾插尾删操作顺序表效率高。
• 顺序表存在下标，支持随机访问，链表不支持随机访问

二、 实现无头、不循环、单向结点

链表可以分为无头结点 含有头结点、循环 不循环、单向与双向。总共可以形成八种不同的链表结构。无头单向不循环链表结构简单基础，需重点掌握。

打印出结点中的数据域

要想打印链表序列中的数据域data，必须要学会遍历链表，无论是打印链表，还是后面的删除插入链表，都需要遍历链表，打印链表可以通过改变head来遍历整个链表，但是删除和插入不能直接通过head来进行操作，防止找不到前面的结点。所以一般情况都借用一个中间变量cur，来遍历整个链表，打印时，循环时cur为空就结束。

   public void display(){
      ListNode cur = head;
      while(cur != null){   //遍历链表
          System.out.print(cur.data+" ");
          cur=cur.next;
      }
      System.out.println();
  }
1
2
3
4
5
6
7
8

查找key是否在单链表当中

遍历链表中序列元素的数据域即可，如果此时的key等于数据域上的数据，则返回true，反之返回false

    public boolean checkIsContains(int key){
        //这里无需判断是否为空，当为空时，直接返回false
        ListNode cur = head;
        while(cur != null){
            if(cur.data==key){
                return true;
            }
            cur=cur.next;
        }
        return false;
    }
1
2
3
4
5
6
7
8
9
10
11

添加结点

添加结点包括头插法，其时间复杂度时O(1),还有尾插和任意位置插入结点，这两种方式时间复杂度为O(n)，需要遍历整个数组，任意位置插入结点，其逻辑大体就是以下操作

    node.next=preNode.next;
    preNode.next=node;
1
2

流程就是

• 找到插入位置的前一个结点
• 插入目标结点

头插法

    public void AddFirst(int number){
        ListNode node = new ListNode(number);
        if(head==null){
            head=node;
        }else{
            node.next=this.head;
            head=node;
        }
    }
1
2
3
4
5
6
7
8
9

尾插法

public void AddLast(int number){
    ListNode node=new ListNode(number);
    if(head==null){
        head=node;
    }else{
        ListNode cur=this.head;
        while(cur.next!=null){
            cur=cur.next;
        }
        cur.next=node;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

任意位置插入

    public void Add(int index,int number){
        //判断下标的合法性
        checkIndex(index);
        ListNode node = new ListNode(number);
        ListNode preNode = head;
        for (int i = 0; i < index-1; i++) {
            preNode=preNode.next;
        }
        if(index==0){
            AddFirst(number);
            return;
        }else if(index==size()){
            AddLast(number);
            return;
        }else{
            node.next=preNode.next;
            preNode.next=node;
        }
    }
    public void checkIndex(int index){
        if(index<0&&index>size()){
            throw new MySingleListIndexOutOfException("index不合法");
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

删除结点

删除第一次出现关键字为key的节点

   public void subOneKeyNode(int key){
        if(head==null){
            System.out.println("链表为空");
            return;
        }
        if(head.data==key){
            head=head.next;
            return;
        }
        //1. 找到要删除的结点的前一个结点
        ListNode cur=this.head;
        while(cur.next != null){
            if(cur.next.data==key){
                cur.next=cur.next.next;
                return;
            }
            cur=cur.next;
        }
        System.out.println("链表中无data为key的元素");
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

删除所有值为key的节点

    public void subAllKeyNode(int key){
        if(head==null){
            return;
        }
        ListNode cur = head;
        //判断第一个结点的data是否时key
        while(cur.data == key){
            head=head.next;
            cur=head;
            if(cur==null){
                return;
            }
        }
        while(cur.next != null){
            if(cur.next.data==key){
                cur.next=cur.next.next;
            }else{
                cur=cur.next;
            }

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

清除链表，结点置为空

清空结点，可以简单暴力的head=null，这样就丢失链表上的所用结点，但是如果想把每一个链表上的next置为空，就需要借助

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