数据结构——链表、栈、队列

前言

​ 链表、队列、栈，是数据结构中最基础的几个结构，而链表是最基础的。之后的复杂数据结构大都是在其基础上演化出来的。

链表

​ 一种线程数据结构，与数组不同的是，它在内存空间中不一定是顺序存储的，为了保证链表中元素的连续性，一般使用一个指针来找到下一个元素。

使用java实现一个链表链表，首先需要定义一个节点

class Node<T> {
        T       value;
        Node<T> next;

        public Node(T value) {
            this.value = value;
        }
    }

因此，对于链表来说，如果想要根据索引查找元素，只能从头开始，时间复杂度O(N).

如果在Node中增加了前驱节点，那么就会成为双向链表。

Java中的LinkedList就是典型的双向链表。

如果在LinkedList上结合HashMap(Set)就是LinkedHashMap(Set),既保证了元素的有序性，有可以O1获取元素。

一个简单的链表实现如下

package table;
import java.util.Iterator;
//单向链表
//头结点不存元素
//需要一个记录首节点,内容为null；一个记录链表长度
public class LinkList<T> implements Iterable<T>{
    private Node head;//头结点
    private int N;//链表长度
    public class Node<T> {
        T item;                                     //存储元素
        Node next;                                      //指向下一节点 一个Node对象
        public Node(T item, Node next){             //有参构造
            this.item = item;
            this.next = next;
        }
    }
    public LinkList(){//无参初始化
        this.head = new Node(null,null);
        this.N = 0;
    }
    public void clear(){//清空链表：头结点不指向下一个元素
        N=0;
        head.next = null;
    }
    public  boolean isEmpty(){//判断空
        return N==0;
    }
    public int length(){//求长度
        return N;
    }
    public T get(int i){ //获取第i个元素
        //利用循环，从头结点向后遍历，找i次
        Node n = head.next;
        for (int index =0;index <i;index++){
            n = n.next; //循环指向下一个节点
        }
        return (T) n.item;
    }
    public void insert(T t){                                        //添加数据
                                                                    //添加元素只需要将最后一个节点指向新节点
        Node n = head;
        while(n.next!=null){
            n = n.next;                                             //尾节点不为null不能换
        }
        Node newNode = new Node(t,null);
        n.next =newNode;
        N++;
    }
    public void insert(int i,T t){                      //i之前添加数据
                                                        //找到i前的一个节点
        Node pre = head;
        for (int index = 0;index<=i-1;index++){                             ///因为头结点实际循环i-1次
            pre = pre.next;
        }
                                                 //找到i节点
        Node curr = pre.next;
        //创建新节点并指向i
        Node newNode = new Node(t,curr);
        //i之前的节点指向新节点
        pre.next = newNode;
        //加1
        N++;
    }
    public T remove (int i){//删除第i个元素并返回
        //获得i之前的节点
        Node pre = head;
        for (int index = 0;index<=i-1;index++){
            pre = pre.next;
        }
        //找到i
        Node curr = pre.next;
        //找到i后的节点
        Node fur = curr.next;
        //将2者连接后-1
        pre.next = fur;
        N--;
        return (T) curr.item;

    }
    public int indexOf(T t){//返回首次出现元素的序列
        //头结点开始遍历，找到每个节点的元素，取出item与T比较
        Node n = head;
        for (int i =0;n.next!=null;i++){//下一个元素不是null就一直找
            n = n.next;
            if (n.item.equals(t)){
                return i;
            }//没有设置对不存在的这一元素的提醒
        }
        return -1;
    }
    public void reverse(){  //翻转单链表  递归翻转
        if (isEmpty()){
            return;
        }
        else{
            reverse(head.next);
        }
    }
    public Node reverse(Node curr){  //翻转单链表cur,并返回
        if(curr.next==null){
            head.next = curr;
            return curr;
        }
        //递归翻转当前节点的下一个节点
        Node per = reverse(curr.next); //新节点为翻转后的下一节点
        per.next = curr; //新节点的下一个节点为反转前的前一个节点
        curr.next = null; //这个节点设为尾结点
        return curr;
            //不是最后一个节点那么则递归翻转最后一个节点的前一个节点
    }

    @Override
    public Iterator iterator() {

        return new LIterator();
    }
    private class LIterator implements Iterator {
        private Node n;
        public LIterator(){
            this.n = head; ///初始化
        }
        @Override
        public boolean hasNext() { //满足hasNext条件则不断执行next
            return n.next!=null;
        }

        @Override
        public Object next() {
            n = n.next;
            return n.item;
        }
    }
}

算法题中，链表经常出现，比较基础的题型包括：链表的翻转，环判断，环入口，多链表求第K大/小元素等。链表也是实现跳表的基础。

队列/栈

​ 链表和队列本质上是一种特殊的单链表，不同之处在于他们限制了元素的插入/删除顺序。

队列：

​ 对于队列来说，元素从一端进入，从另一端出去，也就是先入的元素先被删除，英文叫做：First In，First Out，简写FIFO。

​ 队列比较经典的使用是在广度优先搜索当中(树的层序遍历其实也是广度优先搜索)。除此之外，队列也可以拥有顺序，称之为优先队列，在java已经有实现，称之为PriorityQueue。

队列实现:

package zhan;
import java.util.Iterator;

//先进先出 栈相比，队列一端进一端出。
public class Queue<T> implements Iterable<T> {
    private class Node<T>{
        public T item;
        public Node next;
        public Node(T item,Node next){
            this.item = item;
            this.next = next;
        }
    }
    private Node head;  //头节点
    private int N;
    private Node last;  //尾
    public Queue(){
        this.head = new Node(null,null);
        this.last = null;
        this.N = 0;
    }
    public boolean isEmpty(){
        return N==0;
    }
    public int size(){
        return N;
    }
    public void enqueue(T t){           //由last插入链表,从首节点依次插入
        if (last == null){
            last= new Node(t,null);
            head.next = last;
        }
        else{
            Node oldlast = last;
            last = new Node(t,null);
            oldlast.next = last;
        }
        N++;
    }
    public T dequeue(){
        if (isEmpty()){
            return null;            //头结点开始删除
        }
        Node oldeFirst = head.next;
        head.next = oldeFirst.next;
        N--;
        //删队列在删除元素，所以需要重置last
        if (isEmpty()){
            last = null;
        }
        return (T)oldeFirst.item;
    }
    @Override
    public Iterator<T> iterator(){
        return new QIterator();
    }
    private class QIterator implements Iterator{
        private Node n;
        public QIterator(){
            this.n = head;
        }
        @Override
        public boolean hasNext() {
            return n.next!=null;
        }

        @Override
        public Object next() {
            n = n.next;
            return (T)n.item;
        }
    }
}

栈：

​ 栈则相反，元素从一端进，就要从一端出。也就是先进后出，英文叫做：First In，Last Out，简称FILO。

​ 栈在算法中经常使用到，诸如括号标点匹配问题，单调栈问题等，递归也是一种特殊的对栈的使用。

stack实现：

package zhan;
import java.util.Iterator;

//链表栈
public class Stack<T> implements Iterable<T>{

    private class Node<T>{      //链表类
        public T item;
        public Node next;
        public Node(T item,Node next){
            this.item =item;
            this.next = next;
        }
    }
    private int N;          //栈元素个数
    private Node head;      //记录头元素
    public Stack(){
        this.N = N;
        this.head = new Node(null,null);
    }
    public boolean isEmpty(){
        return N==0;
    }
    public int size(){
        return N;
    }
    //写压栈
    public void push(T t){
        //找到首节点指向的第一个节点
        Node oldNode = head.next;
        //创建新节点
        Node newNode = new Node(t,null);
        //首节点指向新节点
        head.next = newNode;
        //新节点指向原来的第一节点
        newNode.next = oldNode;
        N++;
    }
    public T pop(){
        //首节点指向第一个节点
        Node oldFirst = head.next;
        //head.next = oldFirst.next不安全，需要校验
        if (oldFirst==null){
            return null;
        }
        head.next = oldFirst.next;
        N--;
        return (T)oldFirst.item;
    }
    @Override
    public Iterator<T> iterator() {
        return new LIterator();
    }
    private class LIterator implements Iterator{
        private Node n;
        public LIterator(){
            this.n = head;
        }
        @Override
        public boolean hasNext() {
            return n.next!=null;
        }
        @Override
        public Object next() {
            n = n.next;
            return n.item;
        }
    }


}