引言

动态数组可能会造成内存空间 “申请的多而使用的少”，链表却可以做到 “使用多少就申请多少”。

1、链表（SingleLinked List）

链表是一种链式存储的线性表，所有元素的内存地址不一定是连续的。

当我们添加一个元素时，首先会创建一个节点（Node）对象，在该节点内部既包含一块用来存放该节点数据的内存空间，又包含一块用来存放下一个节点对象引用（地址）的内存空间。

我们称第一个节点为 “头节点”，最后一个节点为 “尾节点”。

**注：**由于最后一个节点后面是没有下一个节点的，所以其内部存储的下一个节点地址为空（null）。

2、单向链表的设计

（1）类的结构设计

在编程之前，我们需要先对链表类（SingleLinkedList）的结构进行设计。如下图所示：

单向链表类需要的成员主要包括：

链表存放元素的数量。 //private int size;

size = 元素（Element）数目 = 节点（Node）数目。

第一个节点的引用。 //private Node<E> first;

first指向链表的第一个节点。

内部静态节点（Node）类。

由于该节点类仅供链表类使用，因此，需将该节点类定义为链表类的内部类。该类的成员包括：

a. 该节点内部的泛型元素	//E element;

泛型元素既可以是基本数据类型，也可以是类的对象。

b. 下一个节点的引用	// Node/<E> next;

next指向链表的下一个节点。

1
2
3

c. 构造函数

d. 析构函数（Java语言没有）

**注：**内部类的成员可以不写访问权限。

接口函数

**注：**因为链表不需要预先分配内存，所以SingleLinkedList类不用写构造函数。

（2）接口设计

链表的大部分接口和动态数组类似。主要包括：

int size(); //元素的数量
boolean isEmpty(); //是否为空
boolean contains(E element); //是否包含某元素
E get(int index); //获取index位置对应的元素
E set(int index, E element); //设置index位置的元素（覆盖）
void add(E element); //添加元素到尾部
void add(int index, E element); //在index位置添加元素
E remove(int index); //删除index位置对应的元素
int indexOf(E element); //查看元素的位置
void clear(); //清除所有元素

注：接口是供别人在外部通过对象调用的，所以要设计成公有（public）成员。

3、单向链表的实现

3.1 编程实现

新建一个项目，在其中：

先新建一个名称为SingleLinkedList（包名为：com.atangbiji）的类，用来自己实现单向链表；
再新建一个名称为Main（包名为：com.atangbiji）的类，用来调用（测试）自己封装的链表。

接口实现，我们这里直接考虑链表元素均为泛型的情况。

（1）定义私有成员变量和内部静态节点（Node）类

SingleLinkedList.java文件：

package com.atangbiji;

public class SingleLinkedList <E> {
	private int size;	//链表存放元素的数量
	private Node<E> first;	//第一个节点的引用
	
	//内部静态节点类
	private static class Node<E> {
		E element;	//该节点内部的泛型元素
		Node<E> next;	//下一个节点的引用
		
		//构造函数
		public Node(E element, Node<E> next) {
			this.element = element;
			this.next = next;
		}
	}
}

（2）实现size()接口

SingleLinkedList.java文件：

/*
 * 元素的数量
 * @param
 * @return 
 * */
public int size() {
	return size;	//直接返程size成员变量即可
}

（3）实现isEmpty()接口

SingleLinkedList.java文件：

/*
 * 是否为空
 * @param
 * @return 
 * */
public boolean isEmpty() {
	return size == 0;	//size为0为空，否则不为空
}

（4）实现get(int index)接口

获取索引为index的节点对象

为了方便获取任意节点，我们定义一个私有方法Node用来获取索引为index的节点。

SingleLinkedList.java文件：

/*
 * 获取索引为index的节点对象
 * @param: index
 * @return：索引为index的节点对象
 * */
private Node<E> node(int index) {
	//判断索引是否越界
	if (index < 0 || index >= size) {
		throw new IndexOutOfBoundsException("索引出错，Index = " + index +"; Size =" + size);	//抛出异常
	}
	//从前向后找到第index个节点
	Node<E> node = first;
	for (int i = 0; i < index; i++) {
		node = node.next;
	}
	return node;
}

获取节点元素

获取链表索引为index的元素，只需：

1
2
3

a. 先从链表中获取索引为index的节点对象;

b. 再从该节点对象中获取其中的元素即可。

SingleLinkedList.java文件：

/*
 * 获取index位置对应的元素
 * @param: index
 * @return 
 * */
public E get(int index) {
	return node(index).element;
}

（5）实现set(int index, E element)接口

类似地，设置链表索引为index的元素，只需：

1
2
3

① 先从链表中获取索引为index的节点对象;

② 再设置该节点对象中的元素即可。

SingleLinkedList.java文件：

/*
 * 设置index位置的元素（覆盖）
 * @param: index
 * @param: element
 * @return: 原来的元素
 * */
public E set(int index, E element) {
	//从链表中获取索引为index的节点对象
	Node<E> node = node(index);
	E old = node.element;
	//设置该节点对象中的元素
	node.element = element;
	
	return old;
}

（6）实现indexOf(E element)接口

只需遍历链表中的元素，判断链表中是否存在该元素即可。若存在，返回索引。若不存在，返回-1。

链表的indexOf(E element)接口与动态数组的indexOf(E element)接口类似，这里不再赘述。

SingleLinkedList.java文件：

private static final int ELEMENT_NOT_FOUND = -1; //未找到

/*
 *  查看元素的位置
 * @param: element
 * @return: 元素的位置
 * */
public int indexOf(E element) {
	//若元素为空（null）
	if (element == null) {
		//遍历链表
		Node<E> node = first;
		for (int i = 0; i < size; i++) {
			// node.element可以是null，也可以不是null。
			if (node.element == null) {
				return i;
			}
			node = node.next;
		}
	}else {
		//若元素不为空（null）。
		//遍历链表
		Node<E> node = first;
		for (int i = 0; i < size; i++) {
			// node.element可以是null，也可以不是null。
			if(element.equals(node.element))
			{
				return i;
			}
			node = node.next;
		}
	}
	return ELEMENT_NOT_FOUND;
}

（7）实现contains(E element)接口

在链表中查找该元素，若返回值不为-1，则说明该元素存在。

SingleLinkedList.java文件：

/*
 * 是否包含某元素
 * @param: element
 * @return 
 * */
public boolean contains(E element) {
	return indexOf(element) != ELEMENT_NOT_FOUND;
}

（8）实现clear()接口

清空链表只需将所有节点的内存释放，同时将size置为0即可。

SingleLinkedList.java文件：

/*
 * 清除所有元素
 * @param
 * @return
 * */
public void clear() {
	first = null;	//将第一个节点的引用设为空（null），即可实现所有节点的内存释放。
	size = 0;
}

注：Java中，将第一个节点的引用设为空（null），即可实现所有节点的内存释放。

**附：**为了证明该方法的确释放了所有节点的内存，我们同样可以在内部静态节点（Node）类中重写Java中自带的finalize()方法进行测试。测试过程与动态数组泛化后的clear()接口测试方法类似，这里不再赘述。

（9）实现remove(int index)接口

删除链表某一节点的元素只需：

①获取被删除节点的前一节点；

②断开被删除节点与前一节点的连接，并直接将其前一节点与后一节点相连；

③链表存放元素的数量-1。

注意分析头节点（index=0）情况。

SingleLinkedList.java文件：

/*
 * 删除index位置对应的元素
 * @param: index
 * @return: 被删除的元素
 * */
public E remove(int index) {
	//被删除结点
	Node<E> removeNode = node(index);
	
	if (0 == index) {
		//若要删除链表中的第一个元素，直接将first指向第二个元素即可
		first = removeNode.next;
	} else {
		//1、获取被删除节点的前一节点
		Node<E> prevNode = node(index - 1);
		//2、断开被删除节点与前一节点的连接，并直接将其前一结点与后一节点相连
		prevNode.next = removeNode.next;
	}
	
	//3、链表存放元素的数量-1
	size--;
	
	return removeNode.element;
}

（10）实现add(int index,E element)接口

链表添加新元素不用考虑是否需要扩容的问题。

单向链表在index处添加新元素只需：

①创建一个新节点；

②分别获取新节点的前一节点和后一节点；

③断开index结点与前一结点的连接，并将新节点分别与前一节点和后一节点相连；

④链表存放元素的数量+1。

注意分析头节点（index=0）的情况。

SingleLinkedList.java文件：

/*
 * 在index位置添加元素
 * @param: index
 * @param: element
 * @return
 * */ 
public void add(int index,E element) {
	//判断索引是否越界
	if (index < 0 || index > size) {
		throw new IndexOutOfBoundsException("索引出错，Index = " + index +"; Size =" + size);	//抛出异常
	}
	if (0 == index) {
			
		//1、创建一个新结点
		Node<E> newNode = new Node<E>(element,null);
			
		//2、分别获取新节点的前一节点和后一节点
		Node<E> preNode = null;//获取新节点的前一结点（即：index结点的前一结点）
		Node<E> nextNode = first;//获取新节点的后一结点（即：index节点）
			
		//3、断开index结点与前一结点的连接，并将新节点分别与前一节点和后一节点相连
		first = newNode;
		newNode.next = nextNode;
		
	} else {
		
		//1、创建一个新结点
		Node<E> newNode = new Node<E>(element,null);
		
		//2、分别获取新节点的前一节点和后一节点
		Node<E> preNode = node(index - 1);//获取新节点的前一结点（即：index结点的前一结点）
		Node<E> nextNode = preNode.next;//获取新节点的后一结点（即：index节点）
		
		//3、断开index结点与前一结点的连接，并将新节点分别与前一节点和后一节点相连
		preNode.next = newNode;
		newNode.next = nextNode;
	}
	//4、链表存放元素的数量+1
	size++;
}

（11）实现add(E element)接口

add(E element)接口是add(int index,E element)接口的特例。我们只需在size处添加新元素即可。

SingleLinkedList.java文件：

/*
 * 添加元素到尾部
 * @param: element
 * @return 
 * */
public void add(E element) {
	add(size,element);
}

（12）打印链表中的所有元素

同动态数组一样，为了打印对象链表中的所有元素，我们可以通过重写（也称覆盖）toString()方法，并在其中完成字符串的拼接的方式即可实现。

为了更加直观地展现单向链表，我们在输出各节点元素时打印 “该节点元素→下一节点元素”。

**注：**Java中字符串拼接建议使用StringBuilder类。

SingleLinkedList.java文件：

/*
 *  打印链表中的所有元素：重载toString()函数
 *  @param
 *  @return 链表元素
 * */
@Override
public String toString() {
	//新建StringBuilder
	StringBuilder string = new StringBuilder();
	
	//拼接字符串
	string.append("单向链表 size = ").append(size).append("; [");
	Node<E> node = first;
	for (int i = 0; i < size; i++) {
		string.append(node.element);
		//若尾节点指向null，则只打印本节点；否则输出下一节点
		if (node.next != null) {
			string.append("->").append(node.next.element);
		}
		
		if (i != size - 1) {
			string.append(", ");
		}
		
		node = node.next;
	}
	string.append("]");
	
	return string.toString();
}

3.2 接口测试

链表要注意边界测试，如：当index为0、size - 1、size时的情况。

在Main类（Main.java文件）中新建一个SingleLinkedList对象，用来测试自己封装的链表。这里仅以添加和删除元素接口为例进行测试，其它接口的测试方法与此类似，这里不再赘述。

Main.java文件：

package com.atangbiji;

public class Main {
	public static void main(String[] args) {
		SingleLinkedList<Integer> linkedList = new SingleLinkedList <Integer>();
		
		linkedList.add(11);
		linkedList.add(22);
		linkedList.add(33);
		linkedList.add(44);
		linkedList.add(linkedList.size() - 1,null);
		linkedList.add(55);
		linkedList.add(linkedList.size(),66);
		linkedList.add(0,0);
		linkedList.add(0,null);
		
		System.out.println(linkedList);
		
		linkedList.remove(linkedList.size() - 1);
		System.out.println(linkedList);
		
		linkedList.remove(5);
		System.out.println(linkedList);
		
		int linkedListSize = linkedList.size();
		
		for (int i = 0; i < linkedListSize; i++) {
			linkedList.remove(0);
			System.out.println(linkedList);
		}

	}
}