数组和链表是一组简单、常用的，线性的数据结构，java中很多复杂数据结构都是基于它们实现的。虽然简单，但却是面试中的常客，尤其是算法相关的面试题。

数组

数组是一种有序的、固定大小的、存储相同数据类型的线性数据结构。数组有着广泛的应用，比如java中的ArrayList、Vector等数据结构就是基于数组实现的。数组的示意图：

数组的主要特点：

• 插入和删除效率低
• 连续内存，大小固定，无法动态扩展
• 可以根据下标随机访问，查找效率高

链表

链表也是一种线性的数据结构，但链表不是连续内存，而是通过指针指向将元素进行关联。链表的主要特点：

• 插入和删除效率高
• 非连续内存，无固定大小，可以随时扩展
• 无法随机访问，查找效率低

链表一般都会有一个头节点，该节点一般不存储数据，或者存储一些和链表本身相关的信息。链表根据特点又可以分为单向链表、双向链表、双向循环链表。

单向链表

单向链表一般也称为单链表，单链表的示意图：

链表在添加元素时一般有头插法和尾插法两种。

头插法示意图：

尾插法示意图：

双向链表

和单链表一样，它的每个数据结点中都有两个指针，分别指向上一个和下一个节点，也称为前驱节点和后驱节点。从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。

双向链表示意图：

双向循环链表

如果双向链表的头节点既指向第一个节点，也指向最后一个节点；最后一个节点既指向上一个节点，也指向头节点，那么就是双向循环链表。

双向循环链表示意图：

面试题：反转单链表

面试时，有一道出现频率非常高的链表题，反转单链表，一般用于考察面试者的算法基础。

这道题有很多解法，比如通过遍历链表再配合数组或者栈，都是可以实现的。但这并不是面试官想要的答案，面试官想要的是通过直接修改链表指针指向去实现单链表的反转。

解题分析：因为头节点的存在，如果头节点之后只有一个节点，那么无需做任何操作。比如：

该单链表反转之后还是自己。所以：

// 链表为空
if (head == null) {
    return null;
}

// 头节点指向的第一个节点
Node first = head.next;
if (first == null || first.next == null) {
    return head;
}

后面我们就可以通过反转first链表，最后再加上头节点，实现整个链表的反转。假设链表除去头节点，只有两个节点，此时first=node(10)，first.next=node(20)，彼此交换即可实现链表反转。如下图：

Node next = first;
Node current = first.next;
next.next = null;

current.next = next;
// head是头节点
head.next = current;
return head;

最后返回的链表为：

以此内推，我们就能得到这样的一张逻辑推理图：

我们通过代码去实现这个循环：

Node next = first;
Node current = first.next;
next.next = null;

while (current.next != null) {
    Node tmp = current.next;
    current.next = next;
    next = current;
    current = tmp;
}

current.next = next;
head.next = current;
return head;

最后，完整的单链表反转的java代码实现：

/**
 * @descr: 反转单链表
 */
public static Node reverse(Node head) {
    // 链表为空
    if (head == null) {
        return null;
    }

    // 头节点指向的第一个节点
    Node first = head.next;
    if (first == null || first.next == null) {
        return head;
    }

    Node next = first;
    Node current = first.next;
    next.next = null;

    while (current.next != null) {
        Node tmp = current.next;
        current.next = next;
        next = current;
        current = tmp;
    }

    current.next = next;
    head.next = current;
    return head;
}

数组和链表的基本概念就分享到这里，后续还有一系列的相关文章哦，请大家期待~

原文链接：数组和算法

数组和链表

原文：https://www.cnblogs.com/ahhyong/p/14027167.html