【数据结构与算法】【07】数据结构之双向链表

双向链表

上章我们提到了静态链表，这严格来说，并不算是标准的链表

只是以顺序表的方式，间接实现了链表的随机存储功能，以供没有指针功能的语言使用

这节我们开始讲解标准的链表，即以指针方式实现的链表

标准的链表常见的形式有单向链表、双向链表、循环链表三种

顾名思义，单向链表只能向后查找，只有next指针，双向链表可以向前查找，有next和previous两个指针

循环链表是一种特殊的单向链表，它仅仅是将单向链表的尾节点next指向了头节点，主要用来实现循环遍历的功能

由于它们的功能都差不多，所以我们只讲解双向链表的实现就够了

双向链表结构示意图

双向链表代码实现

在Java中，并没有指针这个术语，指针指的是对象在内存中的存储地址

而Java中的类对象，默认就是代表这个对象的内存地址的，可以理解为，Java中的类对象本身就是指针

所以Java实现链表和C++稍有不同，在Java中，data是类对象表示，cursor也是类对象表示

	import java.util.Objects;
	
	//双向链表
	//本实现还有提升空间，可将head和tail作为首尾两个特殊标记节点，不存储数据，这样代码会更简单
	@SuppressWarnings("all")
	public class DoubleLinkedList {
	
	    Node head;
	    Node tail;
	
	    public boolean IsEmpty() {
	        return head == null;
	    }
	
	    public int Size() {
	        int size = 0;
	        Node node = head;
	        while (node != null) {
	            size++;
	            node = node.next;
	        }
	        return size;
	    }
	
	    public void Print() {
	        Node node = head;
	        while (node != null) {
	            System.out.println(node);
	            node = node.next;
	        }
	        int size = Size();
	        System.out.println("Total Size: " + size);
	    }
	
	    //查找指定位置数据
	    public T Find(int index) {
	        Node node = head;
	        for (int i = 0; i