玩转数据结构3-链表

前面两节课程主要介绍了动态数组、栈以及队列这样三种数据结构，这三种数据结构的底层都是依托于静态数组构建的，靠resize解决固定容量的问题。本节课介绍一种真正的动态数据结构-链表，链表也是一种线性数据结构，是最简单的动态数据结构。

1. 链表基础

1.1 链表的特点

• 链表的数据存储在节点(Node)中，节点中还包含下一节点的地址

    class Node{
        E e;
        Node next;
    }
  

• 前面讲到，数组最好用于索引有语意的情形，其最大的优点是支持快速查询

• 而与数组相比，链表的优点是它是一种真正的动态结构，不需要处理固定容量的问题；缺点则是丧失了随机访问的能力

• 链表的基本结构(支持泛型)：

    public class LinkedList<E> {
    	// 私有节点（Node）类
    	private class Node{
    		private E e;
    		private Node next;
    		
    		public Node(E e, Node next) {
    			this.e = e;
    			this.next = next;
    		}
    		
    		public Node(E e){
    			this(e,null);
    		}
    		
    		public Node() {
    			this(null,null);
    		}
    		
    		@Override
    		public String toString() {
    			return e.toString();
    		}
    	}
    	
    	private Node head;
    	private int size;
    	
    	public LinkedList() {
    		head = new Node();
    		size = 0;
    	}
  
    	// 获取链表中的元素个数
    	public int getSize(){
    		return size;
    	}
    	
    	// 返回链表是否为空
    	public boolean isEmpty() {
    		return size == 0;
    	}
    }
  

1.2 添加元素

链表中添加元素分为两种情况：

• 一种是向链表头添加元素
  
  此时需要将链表头(head)作为待添加元素node的下一节点：node.next = head
  
  然后将node赋为新的head节点：head = node;
  

    // 在链表头添加新的元素e
    public void addFirst(E e){
    	Node  node = new Node(e,null);
    	node.next = head;
    	head = node;
    	// head = new Node(e,head);
    	size ++;
    }
  

• 一种是向链表中间添加元素
  例如将node 添加到索引位置为2的位置（非典型应用），关键点在于定义一个prev节点，指向待添加位置的前一个节点
  
  
  找到prev之后，将prev的下一节点赋为node的下一节点: node.next = prev.next
  
  然后将node赋为prev的下一节点：prev.next = node
  

    // 在链表的index（0-based）位置添加新的元素e
    // 非常规方法
    public void add(int index,E e) {
    	if(index<0 || index >=size)
    		throw new IllegalArgumentException("Add failed. Index is illegal. ");
    	if (index == 0) {
    		Node node = new Node(e);
    		node.next = head;
    		head = node;
    	}
    	else {
    		// 从链表头开始，找到索引位置的前一位
    		Node pre = head;
    		for(int i=0;i<index - 1;i++) {
    			pre = pre.next;
    		}
  
    		Node newNode = new Node(e);
    		newNode.next = pre.next;
    		pre.next = newNode;
    		
    		// pre.next = new Node(e,pre.next);
    		size ++;
    	}
    }
  

• 上述实现方法，如果在头节点插入元素，要采取特殊处理，为了避免插入逻辑的不同，可以为链表设立虚拟头节点：
  

  // 设立虚拟头节点的链表  
  public class LinkedList<E> {
    
    private class Node{
    	private E e;
    	private Node next;
    	
    	public Node(E e, Node next) {
    		this.e = e;
    		this.next = next;
    	}
    	
    	public Node(E e){
    		this(e,null);
    	}
    	
    	public Node() {
    		this(null,null);
    	}
    	
    	@Override
    	public String toString() {
    		return e.toString();
    	}
    }
    
    private Node dummyHead;// 虚拟头节点，不存储任何数据
    private int size;
    
    public LinkedList() {
    	dummyHead = new Node();
    	size = 0;
    }
    
    // 获取链表中的元素个数
    public int getSize(){
    	return size;
    }
    
    // 返回链表是否为空
    public boolean isEmpty() {
    	return size == 0;
    }
    
    // 在链表的index（0-based）位置添加新的元素e
    // 使用虚拟链表头，可以不单独处理链表头的插入操作
    public void add(int index,E e) {
    	if(index<0 || index >size)
    		throw new IllegalArgumentException("Add failed. Index is illegal. ");
    	
    	// 从虚拟链表头开始，找到索引位置的前一位
    	Node pre = dummyHead;
    	for(int i=0;i<index;i++) {
    		pre = pre.next;
    	}
    	Node newNode = new Node(e);
    	
    	newNode.next = pre.next;
    	pre.next = newNode;
    	
    	// pre.next = new Node(e,pre.next);
    	size ++;
    }
    
    // 在链表头插入新元素e
    public void addFirst(E e) {
    	add(0,e);
    }
    
    // 在链表尾添加新元素e
    public void addLast(E e) {
    	add(size,e);
    }
  }
  

1.3 链表的遍历、查询和修改

• 在链表中查找元素
  从头节点开始，遍历整个链表，依次对比，找到后返回真，找不到则返回假：

    // 在链表中查找元素
    public boolean contains(E e) {
    	Node cur = dummyHead.next;
    	while(cur!=null) {
    		if(cur.e.equals(e))
    			return true;
    		cur = cur.next;
    	}
    	return false;
    }
  

• 获取链表中指定索引位置的元素
  非典型应用：

    // 获得链表的第index(0-based)个位置的元素
    public E get(int index) {
    	if(index<0 || index >=size)
    		throw new IllegalArgumentException("Get failed. Index is illegal. ");
    	Node cur = dummyHead.next;
    	for(int i = 0;i<index;i++) {
    		cur = cur.next;
    	}
    	return cur.e;
    }
    
    // 获得链表的第一个元素
    public E getFirst() {
    	return get(0);
    }
    
    // 获得链表的最后一个元素
    public E getLast() {
    	return get(size-1);
    }
  

• 修改链表中指定索引位置的元素

    // 修改链表的第index（0-based）个位置的元素为e
    public void set(int index,E e) {
    	if(index<0 || index >=size)
    		throw new IllegalArgumentException("Set failed. Index is illegal. ");
    	Node cur = dummyHead.next;
    	for(int i=0;i<index;i++) {
    		cur = cur.next;
    	}
    	cur.e = e;
    }
  

1.4 链表元素的删除

• 删除索引为2位置的元素
  找到指定索引位置的前一节点prev：
  
  
  
  将prev的下一节点赋为delNode的下一节点：prev.next = delNode.next
  
  将待删除节点delNode的下一节点置为空：delNode.next = null
  

    // 从链表中删除元素e
    public void removeElement(E e) {
    	Node pre = dummyHead;
    	// 从虚拟头节点出发，找到待删除元素的前一节点
    	while(pre.next!=null) {
    		if(pre.next.e.equals(e))
    			break;
    		pre = pre.next;
    	}
    	// 如果找到的前一节点不是最后一个元素，则执行删除操作
    	if(pre.next!=null) {
    		Node delNode = pre.next;
    		pre.next = delNode.next;
    		delNode.next = null;
    		size --;
    	}
    	// 如果找到最后元素，还没有找到元素e
    	else {
    		// throw new IllegalArgumentException("Remove failed. The element is not included in list.");			
    	}
    	
    }
  

2. 使用链表实现栈

2.1 链表的时间复杂度分析

• 添加操作：

函数名	描述	时间复杂度
addLast(e)	在链表尾节点后添加元素，需要遍历整个链表	(O(n))
addFirst(e)	在链表头节点前添加元素，只需一步操作	(O(1))
add(index,e)	在指定索引位置添加元素，计算复杂度期望值	(O(n/2)=O(n))

• 删除操作

函数名	描述	时间复杂度
removeLast(e)	删除链表尾节点，需要遍历整个链表	(O(n))
removeFirst(e)	删除链表头节点，只需一步操作	(O(1))
remove(index,e)	删除指定索引位置的节点，计算复杂度期望值	(O(n/2)=O(n))

• 修改与查找

函数名	描述	时间复杂度
set(index,e)	修改指定索引位置的节点，计算复杂度期望值	(O(n/2)=O(n))
get(index)	获取指定索引位置的节点元素，同上	(O(n))
contains(e)	判断链表中是否存在指定元素，遍历整个链表	(O(n))

仔细观察链表的增删改查操作，如果只对链表头节点进行增删操作，其复杂度均为(O(1))；而修改操作并非常规操作；查找操作如果只查找头节点，时间复杂度也为(O(1))，因此链表的一个典型应用就是实现栈（在同一端增加和删除）。

回顾栈的几个功能函数：

• pop() 弹栈
• push() 压栈
• isEmpty() 判断栈是否为空
• getSize() 栈内元素个数
• peek() 查看栈顶元素

2.2 栈接口

public interface Stack<E> {
	
	int getSize();
	boolean isEmpty();
	E peek();
	E pop();
	void push(E e);

}

2.3 链表数据结构类

public class LinkedList<E> {
	
	private class Node{
		private E e;
		private Node next;
		
		public Node(E e, Node next) {
			this.e = e;
			this.next = next;
		}
		
		public Node(E e){
			this(e,null);
		}
		
		public Node() {
			this(null,null);
		}
		
		@Override
		public String toString() {
			return e.toString();
		}
	}
	
	private Node dummyHead;
	private int size;
	
	public LinkedList() {
		dummyHead = new Node();
		size = 0;
	}
	
	// 获取链表中的元素个数
	public int getSize(){
		return size;
	}
	
	// 返回链表是否为空
	public boolean isEmpty() {
		return size == 0;
	}
	
	// 在链表的index（0-based）位置添加新的元素e
	// 使用虚拟链表头，可以不单独处理链表头的插入操作
	public void add(int index,E e) {
		if(index<0 || index >size)
			throw new IllegalArgumentException("Add failed. Index is illegal. ");
		
		// 从虚拟链表头开始，找到索引位置的前一位
		Node pre = dummyHead;
		for(int i=0;i<index;i++) {
			pre = pre.next;
		}
		Node newNode = new Node(e);
		
		newNode.next = pre.next;
		pre.next = newNode;
		
		// pre.next = new Node(e,pre.next);
		size ++;
	}
	
	// 在链表头插入新元素e
	public void addFirst(E e) {
		add(0,e);
	}
	
	// 在链表尾添加新元素e
	public void addLast(E e) {
		add(size,e);
	}
	// 在链表中查找元素
	public boolean contains(E e) {
		Node cur = dummyHead.next;
		while(cur!=null) {
			if(cur.e.equals(e))
				return true;
			cur = cur.next;
		}
		return false;
	}
	
	// 获得链表的第index(0-based)个位置的元素
	public E get(int index) {
		if(index<0 || index >=size)
			throw new IllegalArgumentException("Get failed. Index is illegal. ");
		Node cur = dummyHead.next;
		for(int i = 0;i<index;i++) {
			cur = cur.next;
		}
		return cur.e;
	}
	
	// 获得链表的第一个元素
	public E getFirst() {
		return get(0);
	}
	
	// 获得链表的最后一个元素
	public E getLast() {
		return get(size-1);
	}
	
	// 修改链表的第index（0-based）个位置的元素为e
	public void set(int index,E e) {
		if(index<0 || index >=size)
			throw new IllegalArgumentException("Set failed. Index is illegal. ");
		Node cur = dummyHead.next;
		for(int i=0;i<index;i++) {
			cur = cur.next;
		}
		cur.e = e;
	}
	
	// 从链表中删除index(0-based)位置的元素, 返回删除的元素
	public E remove(int index) {
		if(index<0 || index >=size)
			throw new IllegalArgumentException("Set failed. Index is illegal. ");
		// 从虚拟链表头开始，找到索引前一位的结点
		Node pre = dummyHead;
		for(int i = 0;i<index;i++) {
			pre = pre.next;
		}
		Node cur = pre.next;
		pre.next = cur.next;
		cur.next = null;
		
		size--;
		
		return cur.e;
		
	}
	
	// 从链表删除第一个元素，返回删除的元素
	public E removeFirst() {
		return remove(0);
	}
	
	// 删除链表尾的元素，返回删除的元素
	public E removeLast() {
		return remove(size-1);
	}
	// 从链表中删除元素e
	public void removeElement(E e) {
		Node pre = dummyHead;
		while(pre.next!=null) {
			if(pre.next.e.equals(e))
				break;
			pre = pre.next;
		}
		if(pre.next!=null) {
			Node delNode = pre.next;
			pre.next = delNode.next;
			delNode.next = null;
			size --;
		}
		else {
			// throw new IllegalArgumentException("Remove failed. The element is not included in list.");			
		}
		
	}
	
	@Override
	public String toString() {
		StringBuilder res = new StringBuilder();
		Node cur = dummyHead.next;
		while(cur!=null) {
			res.append(cur+"-->");
			cur = cur.next;
		}
		res.append("NULL");
		return res.toString();
	}
}

2.4 基于链表的栈数据结构

public class LinkedListStack<E> implements Stack<E> {
	// 私有成员变量LinkedList用来存储栈元素
	private LinkedList<E> list;
	
	public LinkedListStack() {
		list = new LinkedList<E>();
	}
	
	@Override
	public int getSize() {
		return list.getSize();
	}
	
	@Override
	public boolean isEmpty() {
		return list.isEmpty();
	}
	@Override
	public void push(E e) {
		list.addFirst(e);	
	}
	
	@Override
	public E pop() {
		return list.removeFirst();
	}
	
	@Override
	public E peek() {
		return list.getFirst();
	}
	
	@Override
	public String toString() {
		StringBuilder res = new StringBuilder();
		res.append("Stack: Top ");
		res.append(list);
		return res.toString();
	}
	
	public static void main(String[] args) {
		LinkedListStack<Integer> stack = new LinkedListStack<>(); 
		for(int i = 0;i<5;i++
			stack.push(i);
			System.out.println(stack);
			// Stack: Top 0-->NULL
			// Stack: Top 1-->0-->NULL
			// Stack: Top 2-->1-->0-->NULL
			// Stack: Top 3-->2-->1-->0-->NULL
			// Top 4-->3-->2-->1-->0-->NULL
		}
		stack.pop();
		System.out.println(stack);
		// Stack: Top 3-->2-->1-->0-->NULL
	}
}

2.5 数组栈与链表栈实现效率对比

import java.util.Random;

public class Main {
	public static double costTime(Stack<Integer> stack,int nCount) {
		
		Random random = new Random();
		long startTime = System.nanoTime();
		for(int i = 0;i<nCount;i++) {
			stack.push(random.nextInt(Integer.MAX_VALUE));
		}
		for(int i = 0;i<nCount;i++) {
			stack.pop();
		}
		
		long endTime = System.nanoTime();
		return (endTime-startTime) / 1000000000.0 ;
		
	}

	public static void main(String[] args) {
		ArrayStack<Integer> stack = new ArrayStack<>(); 
		for(int i = 0;i<5;i++) {
			stack.push(i);
			System.out.println(stack);
			// Stack: [0] top
			// Stack: [0,1] top
			// Stack: [0,1,2] top
			// Stack: [0,1,2,3] top
			// Stack: [0,1,2,3,4] top
		}
		stack.pop();
		System.out.println(stack);
		// Stack: [0,1,2,3] top
		
		int nCount = 100000;
		ArrayStack<Integer> arraystack = new ArrayStack<>(); 
		LinkedListStack<Integer> linkedstack = new LinkedListStack<>(); 
		
		System.out.println("ArrayStack:"+costTime(arraystack,nCount)); // 0.077
		System.out.println("LinkedListStack:"+costTime(linkedstack,nCount)); // 0.036
			
	}
}

可以看到使用链表实现栈和使用数组实现栈，两者之间的效率是一致的，这与前一节的时间复杂度分析相互映证。

3. 使用链表实现队列

队列的特征是一端进，另一端出，因此上述链表结构并不适合用来实现队列，需要对结构进行一定的改进。

对上述链表结构增加一个tail标签来标记尾节点的位置，从head和tail端增加元素，都只需要一步操作：

• head端: head = new Node(e,head)
• tail端：tail.next = new Node(e); tail = tail.next;

而删除操作：

• head端(一步操作)：head = head.next;
• tail端：遍历整个链表找到前一节点prev

因此，使用改进后的链表结构实现队列，从head端出队，tail端进队：

3.1 队列接口

public interface Queue<E> {
	int getSize();
	boolean isEmpty();
	void enqueue(E e);
	E getFront();
	E dequeue();
}

3.2 私有节点类

private class Node{
	private E e;
	private Node next;
	
	public Node(E e,Node next) {
		this.e = e;
		this.next = next;
	}
	
	public Node(E e) {
		this.e = e;
		next = null;
	}
	
	public Node() {
		this(null,null);
	}
	
	@Override
	public String toString() {
		return e.toString();
	}
}

3.3 链表队列

public class LinkedListQueue<E> implements Queue<E> {
	private int size;
	private Node head;
	private Node tail;
	
	public LinkedListQueue() {
		head = new Node();
		tail = new Node();
		size = 0;
	}
	
	@Override
	public int getSize() {
		return size;
	}
	
	@Override
	public boolean isEmpty() {
		return size == 0;
	}
	
	@Override
	// 从tail端入队
	public void enqueue(E e) {
		// 如果队列为空，head，tail均指向第一个入队元素
		if(isEmpty()) {
			tail = new Node(e);
			head = tail;
		}
		// 队列不为空，则添加到尾节点，并维护tail指向
		else {
			tail.next = new Node(e);
			tail = tail.next;			
		}
		size ++;	
	}
	
	@Override
	// 从head端出队,返回出队元素
	public E dequeue() {
		// 若队列为空，抛异常
		if(isEmpty())
			throw new IllegalArgumentException("dequeue Failed. The queue is empty.");
		// 队列不为空，删除头节点，维护head指向
		Node delNode = head;
		head = head.next;
		// 删除后，若队列为空，维护tail指向（若不维护，tail仍指向待删除元素）
		if(head == null) {
			tail = null;
		}
		delNode.next = null;
		size --;
		return delNode.e;
	}
	
	@Override
	public E getFront() {
		if(isEmpty())
			throw new IllegalArgumentException("Get Failed. The queue is empty.");
		return head.e;
	}
	
	@Override
	public String toString() {
		StringBuilder res = new StringBuilder();
		res.append("Queue: head ");
		Node cur = head;
		while(cur != null) {
			res.append(cur.e+"<-");				
			cur = cur.next;
		}
		res.append("tail");
		return res.toString();
	}
	
	public static void main(String[] args) {
		LinkedListQueue<Integer> queue = new LinkedListQueue<>();
		for(int i = 0;i<10;i++) {
			queue.enqueue(i);
			System.out.println(queue);
			if(i%3==2) {
				queue.dequeue();
				System.out.println(queue);
//				Queue: head 0<-tail
//				Queue: head 0<-1<-tail
//				Queue: head 0<-1<-2<-tail
//				Queue: head 1<-2<-tail
//				Queue: head 1<-2<-3<-tail
//				Queue: head 1<-2<-3<-4<-tail
//				Queue: head 1<-2<-3<-4<-5<-tail
//				Queue: head 2<-3<-4<-5<-tail
//				Queue: head 2<-3<-4<-5<-6<-tail
//				Queue: head 2<-3<-4<-5<-6<-7<-tail
//				Queue: head 2<-3<-4<-5<-6<-7<-8<-tail
//				Queue: head 3<-4<-5<-6<-7<-8<-tail
//				Queue: head 3<-4<-5<-6<-7<-8<-9<-tail
			}
		}
	}
}

4. 总结

本节课主要学习了具有真正的动态数据结构的链表，链表是最简单的动态数据结构，其主要特点是不需要处理固定容量的问题。课程首先分析了链表的结构特性，然后依次实现了链表的增删改查操作。结合链表的时间复杂度分析结果，使用链表实现了前一节介绍的栈结构，并进一步改进链表结构，实现了队列功能。关于链表，还有双向链表等一些特殊的结构，这里暂不讨论，目前主要的工作是拓展学习的广度，后续用到时再进一步深度研究。