【数据结构】模拟实现无头单向非循环链表

链表的概念

学过ArrayList后我们知道它的底层是用数组来存储元素的，是连续的存储空间，当我们要从ArrayList任意位置删除或插入元素时，我们要把后续整体向前或后移动，时间复杂度为O(n)，效率比较低，因此ArrayList不适合做需要过多任意位置插入或删除的场景，这种场景我们使用LinkedList（链表）比较合适。
链表的一个节点分为值域（存储的是节点的值）和指针域（存储的是下一个节点的地址），链表的逻辑顺序是连续的，但物理地址不一定是连续的因为节点是从堆中申请出来的，从堆中申请的空间是按照一定的策略分配的，两次申请的空间可能是连续的，也有可能不连续。

模拟实现无头单向非循环链表

//无头单向非循环链表实现
public class SingleLinkedList {
    
    static class ListNode{
        public int val;//节点值域
        public ListNode next;//节点指针域  下一个节点的地址

        public ListNode(int val) {
            this.val = val;
        }
    }

    ListNode head;//当前链表的头节点

    //初始化一个简单的链表
    public void createList(){
        ListNode node1 = new ListNode(11);
        ListNode node2 = new ListNode(22);
        ListNode node3 = new ListNode(33);
        ListNode node4 = new ListNode(44);
        ListNode node5 = new ListNode(55);

        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        this.head = node1;
    }
}
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

链表常用的方法

//头插法
public void addFirst(int data)
    
//尾插法
public void addLast(int data)

//任意位置插入,第一个数据节点为0号下标
public void addIndex(int index,int data)

//查找是否包含关键字key是否在单链表当中
public boolean contains(int key)

//删除第一次出现关键字为key的节点
public void remove(int key)

//删除所有值为key的节点
public void removeAllKey(int key)

//得到单链表的长度
public int size()

//清除链表
public void clear()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

实现addFirst方法（头插法）

public void addFirst(int data) {
	ListNode node = new ListNode(data);
    //让要插入的节点的指针域指向头节点
	node.next = head;
    //让插入的节点成为头节点
	head = node;
}
1
2
3
4
5
6
7

实现addList方法（尾插法）

要实现尾插法，我们就必须要找到最后一个节点，所以我们要遍历链表，遍历链表的时候我们可以定义一个节点指向头节点然后让定义的节点向后去遍历链表

public void addLast(int data) {
	ListNode node = new ListNode(data);
    //定义一个节点cur指向头节点
	ListNode cur = head;
	//判断链表是否为空 如果为空就直接插入
	if (cur==null){
		head = node;
		return;
	}
    //遍历链表找到最后一个节点
	while (cur.next!=null){
		cur = cur.next;
	}
    //插入节点
	cur.next = node;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

实现size方法（获取链表的长度）

public int size() {
    //定义一个变量来记录链表长度
	int count = 0;
	ListNode cur = head;
    //遍历链表
	while (cur!=null){
		count++;
		cur = cur.next;
	}
	return count;
}
1
2
3
4
5
6
7
8
9
10
11

实现addIndex方法（在任意位置插入元素）

public void addIndex(int index, int data) {
    //判断要插入的位置是否合法
	if (index<0||index>size()){
		System.out.println("index 不合法"+index);
		return;
	}
    //index为0 我们使用头插
	if (index==0){
		addFirst(data);
		return;
	}
    //index等于链表的长度我们可以使用尾插
	if (index==size()){
		addLast(data);
		return;
	}
    
	ListNode node = new ListNode(data);
	ListNode cur = head;
    
	for (int i = 0; i < index-1; i++) {
		cur = cur.next;
	}
	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

实现contains方法（查找是否包含关键字key是否在单链表当中）

public boolean contains(int key) {
	ListNode cur = head;
    //如果链表为空直接返回false
	while (cur!=null){
        //判断是否是key 是返回true 不是则遍历下一个节点
		if (cur.val==key){
			return true;
		}
		cur = cur.next;
	}
	return false;
}
1
2
3
4
5
6
7
8
9
10
11
12

实现remove方法（删除第一次出现关键字为key的节点）

我们可以先定义一个方法查看key是否在链表中

private ListNode searchKey(int key){
	ListNode cur = head;
	while (cur.next!=null){
        //判断cur是否是要删除节点的前一个节点
		if (cur.next.val==key){
			return cur;
		}
		cur = cur.next;
	}
	return null;
}
1
2
3
4
5
6
7
8
9
10
11

public void remove(int key) {
    //判断链表是否为空
	if (head==null){
		return;
	}
    //判断头节点是否为要删除的节点
	if (head.val==key){
		head = head.next;
		return;
	}
    //查找key是否在链表中 不在则返回null
	ListNode cur = searchKey(key);
	if (cur==null){
		System.out.println("没有key的节点"+key);
		return;
	}
    //因为cur是要删除节点的前一个节点 所以cur.next才是要删除的节点
	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

实现removeAllKey方法（删除所有值为key的节点）

public void removeAllKey(int key) {
    //判断链表是否为空
	if (head==null){
		return;
	}
    //要删除节点的前驱
	ListNode prev = head;
    //要删除的节点
	ListNode cur = head.next;
    //遍历链表 从第二个节点开始
	while (cur!=null){
		if (cur.val == key){//删除节点
			prev.next = cur.next;
			cur = cur.next;
		}else {//继续遍历链表
			prev = cur;
			cur = cur.next;
		}
	}
    //在这时我们还剩下头节点没有遍历
	if (head.val==key){
		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
24

实现clear方法（清除链表）

//只需将头节点置为空即可
public void clear() {
	head = null;
}
1
2
3
4