还债系列之数据结构——数组和链表

时间：2023-02-16 00:25:31

读本科的时候，专业没有开数据结构这门课，但是也觉得无所谓，因为直接使用一些框架和Java内置的特性，所以不是很重视数据结构，没有直接面对数据结构的问题，但是随着遇到的问题越来越多，发现如果对数据结构不是很熟悉的话，很多都是无法理解的，甚至出现误解，比如MySQL的索引，简直懵圈！！

一、数组

对于数组这种数据结构，很多编程语言都将它内置在自己的语言规范中，比如熟知的C/C++、Java等等，可以称之为最简单的数据结构，一般来说，对于这种数据结构，在内存中数据是连续存储的（可能也有例外，这与厂商具体的实现有关），而且对这种数据结构的使用也有不同的方式，但是它的一般特点如下：

  • 长度固定
  • 下标标识位置
  • 元素可以重复

由于使用数组时，可以指定是有序的还是无序的，对于这两种不同的类型，数组操作的效率是不同的：

  • 无序数组（通常的使用方式）：
    • 优点：插入快（直接在后面添加即可）
    • 缺点：查找慢（需要顺序查找，O(n)）、删除慢
  • 有序数组：
    • 优点：查找快（可以二分法查找，O(log(n))）
    • 缺点：插入慢（需要维护数组顺序）、删除慢

从上面可以看到不管是哪种使用方式，删除的速度都是很慢的，这是由于要将已删除元素后面的元素全部向前移，这样才能保持数据连续存储，并且可以由下标寻址。
在Java的集合框架中ArrayList就是通过数组来实现的。

二、链表

在链表中，数据是离散存储，至少从逻辑上看是这样的。链表是一种线性结构，可以想象成一条锁链，其中的每个铁环一环套一环，因为在链表中最重要的元素是其中的节点以及节点之间的关系，一句其中的元素构成的复杂程度又可以分为单向链表和双向链表，它们的一般特点如下：

  • 长度不固定
  • 元素可以重复
  • 元素按照插入的顺序存储

链表分为单向链表和双向链表，它们唯一的区别是在链表中的节点维护的关系是单向的还是双向的。

2.1单向链表

所谓单向链表，就是查找元素的时候只能向同一个方向进行，比如链表只维护了向后或者向前的关系。下面通过一个简单的例子，完成针对链表的构造和其中数据的操作，包括增加和查找。

链表中的节点类：

public class Node<T> {
private T data;
// 只维护向后的关系，说明是单向链表
private Node<T> next;

public Node(T data){
this.data = data;
    }
public T getData() {
return data;
    }
public void setData(T data) {
this.data = data;
    }
public Node<T> getNext() {
return next;
    }
public void setNext(Node<T> next) {
this.next = next;
    }
}

链表类：

public class NodeList<T> {
private int length = 0;
// 链表头节点
private Node<T> head;
// 链表尾节点
private Node<T> tail;

public NodeList(){}

public Node<T> head(){
return head;
    }
public Node<T> tail(){
return tail;
    }
// 增加节点
public boolean add(T e){
        Node<T> newNode = new Node<T>(e);
if(length == 0){
            head = newNode;
            tail = head;
        } else {
            tail.setNext(newNode);
            tail = newNode;
        }
        length++;
return true;
    }
// 查询节点，通过顺序
public T get(int index){
        Node<T> result = null;
int i = 0;
for(Node<T> item = head; item != null; item = item.getNext()){
if(i == index){
                result = item;
break;
            }
            i++;
        }
return result == null? null: result.getData();
    }
}

2.2 双向链表

有些操作在单向链表是很难操作的，比如删除一个节点，其实操作很简单，就是将节点的prev节点指向它的next节点即可，但是由于单向链表中只保存了单向的关系，无法获取prev节点。但是在双向链表中就简单了，在双向链表中，一个节点会保存它的前一个节点和后一个节点。此时的节点类变成如下：

public class Node<T> {
private T data;
// 下一个节点
private Node<T> next;
// 前一个节点
private Node<T> prev;

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

public T getData() {
return data;
    }
public void setData(T data) {
this.data = data;
    }
public Node<T> getNext() {
return next;
    }
public void setNext(Node<T> next) {
this.next = next;
    }
public Node<T> getPrev() {
return prev;
    }
public void setPrev(Node<T> prev) {
this.prev = prev;
    }
}

在NodeList中可以很容易的添加删除节点的操作，如下：

public boolean remove(T e){
boolean flag = false;
    Node<T> item = head;
while(item != null){
if(item.getData() == null || item.getData().equals(e)) {
            Node<T> prev = item.getPrev();
            Node<T> next = item.getNext();
// handle prev
if(prev == null){
                head = next;
            } else{
                prev.setNext(next);
                item.setPrev(null);
            }
// handle next
if(next == null){
                tail = prev;
            } else{
                next.setPrev(prev);
                item.setNext(null);
            }
            length--;
            flag = true;
            item.setData(null);
break;
        } else{
            item = item.getNext();
        }
    }
return flag;
}

另外由于要维护双向的关系，所以在add方法中要做一些修改，增加对前节点的关系，如下：

public boolean add(T e){
    Node<T> newNode = new Node<T>(e);
if(length == 0){
        head = newNode;
        tail = head;
    } else {
        tail.setNext(newNode);
        newNode.setPrev(tail);
        tail = newNode;
    }
    length++;
return true;
}

通过对两种链表的描述和简单实现，可以看出一些特点：

  • 查找慢：基本上每次查找都要从头遍历一次，时间复杂度为O(n)；
  • 插入/删除快：只要新增一个节点，然后改变关系即可，虽然数据插入也很快，但是这是在分配的内存范围之内，如果要超出这个范围，就要再进行内存分配，而链表不受长度限制，时间复杂度为O(1)；
  • 空间占用会大一些：使用这种数据结构，数据在内存中是离散存储的，因为链表中的每个节点都要存储上一个和下一个节点的地址，因此占用空间要大一些；

在Java的集合框架中LinkedList就是通过链表来实现的，而且它提供的功能更为完善。
标签：

相关文章