Jerry的知识索引

外观

数组和链表

约 1295 字大约 4 分钟

数据结构和算法

2017-11-23

背包、队列和栈是三种简单的数据类型。那么我们如何去组织（实现）上述的数据类型呢？这时候就要用到 数组 和 链表 了。

一、数组

数组，简单来说就是将所有的数据排成一排存放在系统分配的一个内存块上，通过使用特定元素的索引作为数组的下标，可以在常数时间内访问数组元素的这么一个结构。

数组的优点

  • 简单、易用
  • 访问元素快（常数时间）

数组的缺点

  • 大小固定：数组在使用前必须先制定固定的大小，可能会造成浪费或者不够用溢出
  • 连续空间块：数组初始分配空间时，有时候无法分配能存储整个数组的内存空间（当数组规模太大时）
  • 插入操作实现复杂：往一个大数组中间插入数据，插入索引后面的数据都要相应地往后移动，这会造成很大的开销

二、链表

链表是一种递归的数据结构。它或者为空（null），或者是指向一个结点（node）的引用，该结点含有一个泛型元素和一个指向另一条链表的引用。对于链表来说，初始时仅需要分配一个元素的存储空间。添加新的元素也很容易，不需要做任何内存复制和重新分配的操作。

链表的优点

  • 动态，大小不固定
  • 离散，在内存空间里存储不必连续

链表的缺点

  • 没有随机访问的能力，访问一个元素必须先访问它的上一个元素
  • 链表中的额外指针引用需要浪费内存

链表操作

1. 定义结点

我们这里将 item 定义为 String 类型。当然，根据具体需要，可以替换成 Integer 或其他任何类型。或者，可以把它声明为泛型。

private class Node{
  String item;
  Node next; // Node 里面包含了它自己类型的变量，我们把这种数据结构成为递归的数据结构。
}

2. 访问链表

如果有一个链表的对象实例 first，那么我们可以用 first.item 和 first.next 访问它的实例变量。

3. 构造链表

//创建三个链表对象实例
Node first = new Node();
Node second = new Node();
Node third = new Node();

//每个实例的值
first.item = "to";
second.item = "be";
third.item = "or";

//指向下一个实例
first.next = second;
second.next = third;

我们先 new 了三个链表对象实例，然后给他们的Item赋值，并让他们的next指向下一个链表的引用。

在这里，third.next是null，也就是third.next指向了一个空链表。

链表表示的是一列元素。

4. 在表头插入结点

//步骤一：保存原来的表头
Node oldfirst = first;

//步骤二：创建新的首结点
first = new Node();

//步骤三：设置新结点的实例变量
first.item = "not";
first.next = oldfirst;

5. 删除头结点

first = first.next;

6. 在表尾插入结点

//步骤一：保存指向尾结点的链接
Node oldlast = last;

//步骤二：创建新的尾结点
last = new Node();
last.item = "not";

//步骤三：将尾链接指向新结点
oldlast.next = last;

如果事先不知道 last 节点的引用，则需要一直遍历到尾节点。

// 添加节点到链表尾部
Node head;
// 新节点
last = new Node();
last.item = "real last";

add(last);

public void add(Node newNode) {
    if (head == null) {
        head = newNode;
        return;
    }
    
    Node current = head;
    while (current.next != null) {
        current = current.next;
    }
    current.next = newNode;
}

7. 遍历链表

遍历链表的固定模式：

for (Node i = first; i != null; i = i.next){
    
}

8. 反转链表

迭代实现：

/*
    1、 prev -> current -> next 
    2、 prev <- current    next   这里 current 到 next 的连接断开了，所以必然需要一个临时变量来保存
    3、           prev     current ->  next 
    4、           prev <-  current     next 
*/
public void reverseIterative(Node head) {
    Node prev = null;
    Node current = head;
    Node next = null;

    while(current != null){
      next = current.next;  // 先保存，以免断开后找不到
      current.next = prev;  // 反转指针，此时原链条被切断
      prev = current;       // 反转完成后，往后移动处理下一个节点
      current = next;
    }

    head = prev; 
}

递归实现：

  1. 递归退出条件：没有下一个节点时
  2. head.next是下一个节点，head.next.next = head;把下一个节点的下一个节点设置为当前节点，即反转
  3. head.next = null 将当前的下一个节点设置为 null ，这一步是处理反转到最后的节点（即原链表的第一个节点）
public Node reverse(Node head) {
    if (head.next == null){
        return head;
    }
    Node last = reverse(head.next);
    head.next.next = head;
    head.next = null;
    return last;
}

扩展：反转链表的前N个节点 leetcode 92. 反转链表 II

环形链表

将链表的尾节点指向头节点（首尾相接），就得到一个环形链表。

双向链表

即有指向下一个节点的引用，也有指向上一个节点的引用的链表。

private class Node{
  String item;
  Node next; // 指向下一个节点
  Node prev; // 指向上一个节点
}
贡献者: jerrysheh