数据结构:链表(进击的Java新人Week.4学习笔记)

Author: Harry

一、单链表

说到链表，我们可以结合数组的一些特性进行分析。数组和链表都有各自的特性，下面我们就先从数组的一些局限性进行分析。

数组

基本的数组操作我就不再讲了，我们可以定义一个大小为5的数组a，然后初始化一些数据a[0]=1，a[1]=2，a[2]=3，如图。

现在想要在数组的第三个位置插入一个数，这时数组执行的操作将a[2]的数据拿出，然后再插入到a[3],最后将数据插入a[2]。

如果插入数据时发现数组的容量已经满了，这时操作就更加麻烦了，需要初始化一个更加大容量的数组将原有的数据拷贝到新数组，然后再执行插入操作。
这里只说了插入操作，同样的删除操作也是一个麻烦的事情。这时候我们就可以使用链表进行操作，可以体现出链表的优势。

链表

通过上面看到一些数组的局限性，从而我们就想有没有什么方法可以避免数组的容量局限性。
这样我们就想到了链表，链表可以快速的实现增删改操作而不必关注扩容问题,链表的概念我就不过多赘述了，如图：

在链表中插入一项：

首先来看一下我定义的一个单链表节点：

public class Node {
    private int data;
    private Node next;
    public Node(int data){
        this.data = data;
    }

    public int getData() {
        return data;
    }

    public void setData(int data) {
        this.data = data;
    }

    public Node getNext() {
        return next;
    }

    public void setNext(Node next) {
        this.next = next;
    }
}

这是一个简单的链表结构，包含的内容有data和next，后面会讲到双链表和泛型的结合使用。
这里是单链表的一些简单操作：

import singlelink.module.Node;

public class SingleLink {
    public int size;
    private Node first;
    private Node last;

    public SingleLink(){
        size = 0;
        this.first = null;
        this.last = null;
    }

    public boolean insertLast(int data){
        if(this.first == null){
            first = new Node(data);
        }else {
            Node node = new Node(data);
            last.setNext(node);
            last = node;
        }
        size++;
        return true;
    }

    public boolean insertFirst(int data){
        if(first == null){
            first = new Node(data);
            last = first;
        }else {
            Node node = new Node(data);
            node.setNext(first);
            first = node;
        }
        size++;
        return true;
    }

    public boolean insertByIndex(int index, int data){
        if(index > (size + 1) || index < 1 ){
            return false;
        }else if(index == 1){
            insertFirst(data);
        }else {
            Node node = new Node(data);
            Node tmp = first;
            for(int i = 1; i < index - 1; i++ ){
                tmp = tmp.getNext();
            }
            node.setNext(tmp.getNext());
            tmp.setNext(node);
        }
        size++;
        return  true;
    }

    public boolean deleteByIndex(int index){
        if(index > size || index <= 0){
            return false;
        }else if(index == 1){
            Node node = first.getNext();
            first = node;
        }
        else {
            Node tmp = first;
            for(int i = 1; i <= index - 2; i++){
                tmp = tmp.getNext();
            }
            tmp.setNext(tmp.getNext().getNext());
        }
        size--;
        return true;
    }

    public boolean queryData(int data){
        Node temp = first;
        int index = 1;
        while (temp != null){
            if(temp.getData() == data){
                System.out.println("found data and it index is: " + index);
                return true;
            }
            index++;
            temp = temp.getNext();
        }
        return false;
    }
    
    public void display(){
        Node node = first;
        System.out.println("first -> last :");
        while (node != null){
            System.out.print(node.getData() + "->");
            node = node.getNext();
        }
    }

}

我们可以看到，链表在增删改的时候是比较好操作的，刚好避免了数组这一方面的不足，不用担心扩容的问题。
但是链表有优势的同时也有不足，在查找的时候，每一次都需要从头到尾遍历一次，使得时间复杂度变高。

二、双链表

双向链表，顾名思义就是可以通过对当前节点，可以知道上一个节点和下一个节点，如图：

链表的节点定如下：

public class Node<T> {
    private Node<T> left;
    private Node<T> right;
    private T data;
    public Node(T data){
        this.data = data;
    }

    public Node<T> getLeft() {
        return left;
    }

    public void setLeft(Node<T> left) {
        this.left = left;
    }

    public Node<T> getRight() {
        return right;
    }

    public void setRight(Node<T> right) {
        this.right = right;
    }

    public T getData() {
        return data;
    }

    public void setData(T data) {
        this.data = data;
    }
}

这里我使用到了泛型来定义节点，这里同样的含有data，只不过这里的data我没有指定类型，可以方便存储不同类型的数据，在例子中我使用到的是User对象，如下：

public class User {
    private String name;
    private int age;

    public User(String name, int age){
        this.name = name;
        this.age = age;
    }
    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public int getAge() {
        return age;
    }

    public void setAge(int age) {
        this.age = age;
    }

    @Override
    public String toString() {
        return "User{" +
                "name='" + name + '\'' +
                ", age=" + age +
                '}';
    }
}

链表中的操作如下：

import doublelink.module.Node;
import java.util.Comparator;

public class DoubleLink<T> {
    private int size;
    private Node<T> first;
    private Node<T> last;
    public DoubleLink(){
        this.size = 0;
        this.first = null;
        this.last = null;
    }

    public int getSize() {
        return size;
    }

    public boolean insertFirst(T data){
        if(first == null){
            first = new Node<T>(data);
            last = first;
        }else {
            Node<T> temp = new Node<T>(data);
            temp.setRight(first);
            first.setLeft(temp);
            first = temp;
        }
        size++;
        return true;
    }

    public boolean insertLast(T data){
        if(first == null){
            first = new Node<T>(data);
            last = first;
        }else {
            Node<T> node = new Node<T>(data);
            node.setLeft(last);
            last.setRight(node);
            last = node;
        }
        size++;
        return true;
    }

    public T queryData(int index){
        if(index < 1 || index >size){
            System.out.println("You input index invalid!");
            return null;
        }
        else if(index == 1){
            return first.getData();
        }else {
            Node<T> temp = first;
            for(int i = 1; i <= index - 1; i++){
                temp = temp.getRight();
            }
            return temp.getData();
        }
    }

    public void display(){
        Node<T> node = first;
        while (node != null){
            System.out.print(node.getData().toString() + "->");
            node = node.getRight();
        }
    }

    public boolean remove(Object o) {
        if (o == null) {
            for (Node<T> x = first; x != null; x = x.getRight()) {
                if (x.getData() == null) {
                    unlink(x);
                    return true;
                }


            }
        } else {
            for (Node<T> x = first; x != null; x = x.getRight()) {
                if (o.equals(x.getData())) {
                    unlink(x);
                    return true;
                }
            }
        }
        return false;
    }

    public boolean removeFirst(){
        if(size > 0){
            unlink(first);
            return true;
        }else {
            return false;
        }
    }

    public boolean removeLast(){
        if(size > 0){
            unlink(last);
            return true;
        }else {
            return false;
        }
    }

    T unlink(Node<T> x) {
        final T element = x.getData();
        final Node<T> right = x.getRight();
        final Node<T> left = x.getLeft();

        if (left == null) {
            first = right;
        } else {
            left.setRight(right);
            x.setLeft(null);
        }

        if (right == null) {
            last = left;
        } else {
            right.setLeft(left);
            x.setRight(null);
        }

        x.setData(null);
        size--;
        return element;
    }

    public T removeByComparator(T data,Comparator<T> comparator){
        if(comparator == null){
            return null;
        }else {
            for (Node<T> x = first; x != null; x = x.getRight()) {
                if (comparator.compare(data, x.getData()) == 0) {
                    return unlink(x);
                }
            }
        }
        return null;
    }
}

我需要讲一下的是remove操作，这里我使用了两种remove的方法，一种的仿照JDK的remove方法，是通过equal比较对象是否为同一个，然后再删除，这个需要查找到已经存在的对象，才能删除。
另外一种是我使用了Comparator接口，重写了compare方法，从而使得删除数据更加灵活，只需要写一个比较器传入就可以remove了。

这里写了两个比较器，一个是比较所有内容，另外一个只比较名字，可以根据需求定义不同的比较器，灵活性更好。

public class UserAllInfoComparator implements Comparator<User> {
    public int compare(User user1, User user2) {
        if(user1.getName().equals(user2.getName()) && user1.getAge() == user2.getAge()){
            return 0;
        }
        return -1;
    }
}

public class UserNameComparator implements Comparator<User> {
    public int compare(User user1, User user2) {
        if(user1.getName().equals(user2.getName())){
            return 0;
        }
        return -1;
    }
}

三、队列

说到队列，我们大概来看一下Java中容器的关系，如图：

单向队列

单向队列是单向的，只能从一边进来，另一边出去，而且是先进先出，与栈刚好相反。我们可以用数组模拟，也可以用链表实现。其原理如图：

双向队列

双向队列可以重两边进来，同样可以从两边出去，如图：

循环队列

这里有数组实现了一个简单循环队列：

public class Deque {
    private int[] data;
    private int head;
    private int tail;
    private int length;
    private final static int DEFAULT_SIZE = 10;

    public int getLength() {
        return length;
    }
    public Deque(){
        data = new int[DEFAULT_SIZE];
        head = 0;
        tail = 0;
        length = 0;
    }

    public Deque(int size){
        if(size > 0){
            data = new int[size];
        }else {
            data = new int[DEFAULT_SIZE];
        }
        head = 0;
        tail = 0;
        length = 0;
    }

    public boolean isFull(){
        return length == data.length;
    }

    public boolean isEmpty(){
        return length == 0;
    }

    public boolean insertLast(int element){
        if(!isFull()){
            data[tail] = element;
            length++;
            if(!isFull() && tail <= data.length - 2 && (tail + 1 != head)){
                tail++;
            }else if(!isFull() && tail == data.length - 1 && head != 0){
                tail = 0;
            }else if(isFull()){
                tail = head;
            }
            return true;
        }else {
            System.out.println("The queue is full!");
            return false;
        }
    }

    public int removeFirst(){
        if(!isEmpty() && head < data.length - 1){
            head++;
            length--;
            return data[head-1];
        }else if(!isEmpty() && head == data.length - 1){
            head = 0;
            length--;
            return data[data.length - 1];
        }else {
            head = tail;
            System.out.println("The queue is empty!");
            return 0;
        }
    }
}

其实队列的实现使用链表比使用数组好很多，读者可以自己用链表实现一下。