链表的定义

链表是线性表的链式存储结构,由 n 个节点组成,每个节点包含两个元素:数据域和指针域

数据域:存储当前节点的数据

指针域:存储下一个节点或者上一个节点的物理地址。不同的链表维护的指针域不同,比如单向链表只维护一个后继指针,而双向链表维护着后继指针和前向指针

链表的类型

根据链表的结构可以分为:

  • 单向链表
  • 双向链表
  • 循环链表

单向链表

特点

  • 单向链表只有数据域和指向下一个节点的后继指针
  • 单向链表只能沿着后继指针做向后操作,不能向前操作
  • 单向链表也不能从中间插入或者删除一个元素,因为没有前向指针

头指针和头结点

单向链表可以分为有头节点结构的和无头节点结构的

指向第一个节点的指针称为头指针,如果链表有头节点,则头指针指向头节点,如果没有,则指向首节点。

有头节点的结构如图所示:

头指针     头节点         首节点(a0)          a1             a2           尾结点(a(n-1))
  ↓          ↓              ↓              ↓              ↓                ↓ 
head -> [null|next] -> [data|next] -> [data|next] -> [data|next] -> [data|null]
                         ↑     ↑
                      数据域  指针域

头指针指向头节点,头节点的数据域为空,不存储任何数据,也不计入链表的总长度,它的 next 指向首节点

用 java 的面向对象可以这样理解

假设节点抽象为这样:

public class Node<E>{
    private E data;
    private Node<E> next;
}

当我们想用这个节点作为单向链表时,首先得把它 new 出来

Node<Object> head = new Node<>(); 

这段代码定义了一个引用:head,并且把它指向了在堆中的一个 Node 对象

为什么这个引用要叫 head 呢?而不叫 abc,edf 呢?

这是因为 head 其实就是上面所说的头指针,而 Node 对象就是头节点,Node 对象里面的 next 字段就是后继指针,其指向的是下一个节点。

无头节点的结构如图所示:

头指针      首节点(a0)        a1             a2        尾结点(a(n-1))
  ↓          ↓              ↓              ↓              ↓              
head -> [data|next] -> [data|next] -> [data|next] -> [data|null]
          ↑     ↑
       数据域  指针域

头指针指向首节点,首节点的数据域不为空,作为链表的第一个节点,它的 next 指向下节点

根据上面的 java 代码,可以这样抽象的理解

Node<Object> head = new Node<>("abc"); 

这段代码同样定义了一个引用:head,并且把它指向了在堆中的一个 Node 对象

与上面不同的是,Node 对象是根据有参构造函数 new 出的

此时这个 Node 对象作为首节点,也就是第一个节点,它的 data 字段存储的是 “abc” 这个对象。

看到这里,应该对链表的头指针、头节点、首节点、尾节点、数据域、指针域等概念有了较清晰的认识

那么我们在定义节点的时候究竟是要头节点还是不要头节点呢?

其实两种结构都可以,每种结构都有各自的好处

比如有头节点的结构,我们想在首节点处插入一个新的节点,那么只要找到头节点,然后把头节点的后继指针指向新节点,最后再把新节点的后继指针指向原来的首节点就可以了。

如图所示:

头指针     头节点         首节点(a0)          a1             a2           尾结点(a(n-1))
  ↓          ↓              ↓              ↓              ↓                ↓ 
head -> [null|next] -×-> [data|next] -> [data|next] -> [data|next] -> [data|null]
                  ↘     ↗
                [data|next]
                     ↑
                   新节点

但有头节点的结构也有不好的地方,比如遍历的时候要跳过头节点,从首节点开始,因为头节点不计入链表的长度。

无头节点的结构则相反,遍历的时候直接从 0 开始遍历就可以了,但是要在首节点处插入新节点就有点麻烦。

java 实现单向链表

我们要实现两种单向链表,分别是有头结点的无头节点的。

先看一下有头结点的实现方式

定义节点类

节点类有三个字段和两个构造方法

public class Node<E> {

	// 数据域
	private E item;

	// 后继指针
	private Node<E> next;

	// 链表的长度
	private int size;

	public Node() {

	}
	
	private Node(E item, Node<E> next) {
		this.item = item;
		this.next = next;
	}
}

添加新节点

思路:每次添加新节点时,都是在尾部添加,所以得先找出尾结点。

public boolean add(E item) {
	// 新节点
	Node<E> newNode = new Node<>(item, null);

	// 头结点
	Node<E> head = this;
		
	// 循环遍历找到尾节点
	while (head.next != null) {
		head = head.next;
	}
	// 将尾结点的 next 指向新节点
	head.next = newNode;
	size++;
	return true;
}

给定位置插入新节点

思路:单向链表没有前向指针,所以要先找到 index - 1 处的节点,也就是前节点。然后让新节点指向 index 节点,前节点指向新节点。

public boolean add(E item, int index) {
	// 先校验 index 是否合法
	if (!(index >= 0 && index <= size)) {
		throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
	}
	// 临时节点,从头节点开始
	Node<E> temp = this;
	// 循环遍历找到前节点,因为头节点不算入链表的长度,所以从 -1 开始计数
	for (int i = -1; i < index - 1; i++) {
		temp = temp.next;
	}
	// 新节点指向 index 节点
	Node<E> newNode = new Node<>(item, temp.next);
	// 前节点指向新节点
	temp.next = newNode;
	size++;
	return true;
}

删除节点

思路:因为是单向链表,没有前向指针,所以需要遍历找到前节点,然后根据前节点得到后节点,最后让前节点指向后节点。

public boolean remove(int index) {
	if (!(index >= 0 && index < size)) {
		throw new IndexOutOfBoundsException("Index: " + index + ",size: " + size);
	}
	// 临时节点,从头节点开始
	Node<E> temp = this;
	// 循环遍历找到前节点,因为头节点不算入链表的长度,所以从 -1 开始计数
	for (int i = -1; i < index - 1; i++) {
		temp = temp.next;
	}
	// 后节点
	Node<E> next = temp.next.next;
	// 前节点指向后节点
	temp.next = next;
	size--;
	return true;
}

遍历节点

跳过头节点,从首节点开始遍历

public E get(int index) {
	if (!(index >= 0 && index < size)) {
		throw new IndexOutOfBoundsException("Index: " + index + ",size: " + size);
	}
	// 临时节点,从头节点开始
	Node<E> temp = this;
	// 循环遍历找到前节点,因为头节点不算入链表的长度,所以从 -1 开始计数
	for (int i = -1; i < index; i++) {
		temp = temp.next;
	}
	return temp.item;
}

获取链表的长度

直接返回 size 即可

public int size() {
    return size;
}

测试

测试代码

Node<String> node = new Node<>();
node.add("a");
node.add("b");
node.add("c");
node.add("d", 0);
System.out.println(node);
node.remove(1);
System.out.println(node);

测试结果

Node{item=null, next=Node{item=d, next=Node{item=a, next=Node{item=b, next=Node{item=c, next=null}}}}}
Node{item=null, next=Node{item=d, next=Node{item=b, next=Node{item=c, next=null}}}}

这是有头节点结构的单向链表的 java 实现

可以看到头节点的 item=null,也就是上面所说的头节点不存储数据,只存储指向首节点的指针域

关键点

这段代码主要有几个关键点

  • 添加新节点到链表尾部

采用 while 循环,当 next 为 null 时,则说明找到了尾节点,然后再在尾节点处添加新节点

while (current.next != null) {
    current = current.next;
}
  • 给定位置插入新节点

(1) 从 -1 开始遍历

for (int i = -1; i < index; i++) {
    temp = temp.next;
}

(2) 新节点指向 index 节点

Node<E> newNode = new Node<>(item, temp.next);

(3) 前节点指向新节点

temp.next = newNode;
  • 删除节点

(1) 从 -1 开始遍历

for (int i = -1; i < index; i++) {
    temp = temp.next;
}

(2) 前节点指向后节点

// 后节点
Node<E> next = temp.next.next;
// 前节点指向后节点
temp.next = next;
  • 遍历链表

从首节点(有效节点)开始,只要不为null,就输出

for (int i = -1; i < index; i++) {
    temp = temp.next;
}
  • 获取链表的长度

每访问一次节点,size++ 即可

结论

链表本身并不难,刚开始容易被 next 绕晕。。。最好是要先结合各种示意图来理解链表的结构和原理,然后一定要亲自动手敲代码,试着自己用代码去实现,如果实现不了再去看别人是怎么实现的。用代码实现了之后,在反过头来看链表的结构和原理,进一步加深理解,这样反反复复的学习才能真正的掌握链表。

原文链接:https://miansen.wang/2019/07/08/1/