链表

链表

　　链表是采用链式结构存储的线性表。链表中的元素在存储空间中的位置不一定是连续的，所以链表使用结点来存储元素，每个节点中还存储了相邻节点位置信息。由于不是连续存储，存取元素的速度比顺序表差。但是只要存储空间足够，链表就可以动态增加长度，也就是说，相较于顺序表，链表能更快速地进行元素的插入和删除操作。

　　链表需要一个头指针head来表示链表的第一个结点。根据结点中存储的相邻结点信息的不同，链表又可以细分为单向链表和双向链表。若链表的第一个结点和最后一个结点相连，则该链表又可以称为循环链表。

单向链表

　　单向链表的结点中只保存了直接后继结点的位置信息。也就是说，每一个结点中都有一个next指针指向该结点的直接后继结点，若该结点是最后一个结点，则next取null。

　　

　　单向链表的结点结构定义如下：

public class LNode<E> {

    public E data;

    public LNode<E> next;

    public LNode(E data) {
        this.data = data;
    }

}

查找

　　单向链表通过遍历来找到指定位标的结点：从head指向的结点（第一个结点）开始遍历，遍历到next取值为null的结点（最后一个结点）时结束。

public LNode<E> getNode(int index) {
    if (index < 0) throw new ListException("位标不能为负！");
    if (isEmpty()) throw new ListException("链表为空！");
    // 从head指针指向的结点开始
    LNode<E> node = head;
    // index == 0表示当前结点为待查询结点，node.next == null表示当前结点为最后一个结点
    while (index > 0 && node.next != null) {
        node = node.next;
        index--;
    }
    return node;
}

　　可以根据指定元素来查找结点是否存在。

public LNode<E> getNodeByElem(E e) {
    if (isEmpty()) throw new ListException("链表为空！");
    // 从head指针指向的结点开始
    LNode<E> node = head;
    // node == null表示查找不到指定的结点
    while (node != null) {
        if (e.equals(node.data)) break;
        node = node.next;
    }
    return node;
}

插入

　　单向链表的插入分为三种情况：

　　在前面插入结点：插入结点的next指针指向第一个结点，head指针指向插入结点。

　　

　　在后面插入结点：最后一个结点的next指针指向插入结点。

　　

　　在中间插入结点：指定位置的前一个结点的next指针指向插入结点，插入结点的next指针指向指定位置的结点。

　　

public void add(int index, E data) {
    LNode<E> node = new LNode<E>(data);
    // head == null表示链表为空，index == 0表示在前面插入结点
    if (head == null || index == 0) {
        node.next = head;
        head = node;
    } else {
        // 获取指定位置的前一个结点
        LNode<E> n = getNode(index - 1);
        // n.next == null表示在后面插入结点，n.next != null表示在中间插入结点
        node.next = n.next;
        n.next = node;
    }
}

删除

　　单向链表的删除也分为三种情况：

　　删除第一个结点：head指针指向下一个结点。

　　

　　删除最后一个结点：倒数第二个结点的next指针置为null。

　　

　　删除中间的结点：指定结点前一个结点的next指针指向指定结点下一个结点。

　　

public E remove(int index) {
    // head != null表示链表不为空
    if (head != null) {
        E e;
        // index == 0表示删除第一个结点
        if (index == 0) {
            e = head.data;
            head = head.next;
        } else {
            LNode<E> node = head;
            // index == 1表示当前结点是指定结点的前一个结点，node.next.next == null表示当前结点是倒数第二个结点
            while (index > 1 && node.next.next != null) {
                node = node.next;
                index--;
            }
            e = node.next.data;
            node.next = node.next.next;
        }
        return e;
    }
    return null;
}

反转

　　实现单向链表的反转可以通过将第一个结点与之后的结点断开，之后每一个结点在前面插入，最后head指针指向最后一个结点。

public void reverse() {
    // head == null表示链表为空，head.next == null表示链表中只有一个结点
    if (head != null && head.next != null) {
        LNode<E> node = head.next;
        head.next = null;
        while (node != null) {
            LNode<E> n = node.next;
            // 在前面插入当前结点
            node.next = head;
            head = node;
            // 走向下一个结点
            node = n;
        }
    }
}

单向循环链表

　　单向循环链表是第一个结点和最后一个结点相连的单向链表。单向循环链表最后一个结点的next指针指向第一个结点。

　　

　　在单向循环链表中可以添加一个size变量来存储结点个数。

查找

　　单向循环链表可以通过循环查找指定位标的结点。指定位标可以通过对size求模来减少循环次数。

public LNode<E> getNode(int index) {
    if (index < 0) throw new ListException("位标不能为负！");
    if (isEmpty()) throw new ListException("链表为空！");
    index %= size;
    LNode<E> node = head;
    while (index > 0) {
        node = node.next;
        index--;
    }
    return node;
}

　　可以通过指定元素来查找结点是否存在。

public LNode<E> getNodeByElem(E e) {
    if (isEmpty()) throw new ListException("链表为空！");
    LNode<E> node = head;
    do {
        if (e.equals(node.data)) return node;
        node = node.next;
    } while (node != head);   // node == head表示node已经走完一圈
    return null;
}

插入

　　单向循环链表的插入分为两种：

　　在前面插入结点：插入结点的next指针指向第一个结点，最后一个结点的next指针指向插入结点，head指针指向插入结点。

　　

　　在中间插入结点：插入结点的next指针指向指定位置的结点，指定位置的前一个结点的next指针指向插入结点。

　　

public void add(int index, E data) {
    if (index < 0) throw new ListException("位标不能为负！");
    LNode<E> node = new LNode<E>(data);
    if (isEmpty()) {
        // 链表为空表，则创建一个自成环形的结点
        node.next = node;
        head = node;
    } else {
        // 对size求模减少循环次数
        index %= size;
        LNode<E> n;
        if (index == 0) {
            // 在前面插入结点，获取的是最后一个结点
            n = getNode(size - 1);
            head = node;
        } else {
            // 在中间插入结点，获取的是前一个结点
            n = getNode(index - 1);
        }
        node.next = n.next;
        n.next = node;
    }
    size++;
}

删除

　　单向循环链表的删除也分为两种：

　　删除第一个结点：最后一个结点的next指针指向第二个结点，head指针指向下一个结点。

　　

　　删除其他结点：指定结点前一个结点的next指针指向指定结点下一个结点。

　　

public E remove(int index) {
    if (index < 0) throw new ListException("位标不能为负！");
    if (isEmpty()) return null;
    E e = null;
    if (size == 1) {
        e = head.data;
        head = null;
    } else {
        index %= size;
        LNode<E> node;
        if (index == 0) {
            // 获取最后一个结点
            node = getNode(size - 1);
            head = head.next;
        } else {
            // 获取前一个结点
            node = getNode(index - 1);
        }
        e = node.next.data;
        node.next = node.next.next;
    }
    size--;
    return e;
}

反转

　　单向循环链表的反转与单向链表类似，不过需要先定义一个辅助结点保存反转后的最后一个结点，最后一步需要让最后一个结点的next指针指向反转后的第一个结点（head指针指向的结点）。

public void reverse() {
    // size == 0表示链表为空，size == 1表示链表只有一个结点
    if (size <= 1) return;
    // 反转后的最后一个结点为现在的第一个结点
    LNode<E> tail = head;
    // 从第二个结点开始遍历
    LNode<E> node = head.next;
    while (node != tail) {
        LNode<E> n = node.next;
        // 在前面插入结点
        node.next = head;
        head = node;
        // 走向下一个结点
        node = n;
    }
    // 最后一个结点的next指针指向第一个结点
    tail.next = head;
}

双向链表

　　双向链表的结点中保存了直接前驱结点和直接后继结点的位置信息。也就是说，每一个结点中都有一个next指针指向直接后继结点，一个prior指针指向直接前驱结点。

　　

　　双向链表的结点结构定义如下：

public class DuLNode<E> {

    public E data;

    public DuLNode<E> prior;

    public DuLNode<E> next;

    public DuLNode(E data) {
        this.data = data;
    }

}

查找

　　双向链表也是通过遍历找到指定位标的结点。

public DuLNode<E> getNode(int index) {
    if (index < 0) throw new ListException("位标不能为负！");
    if (isEmpty()) throw new ListException("双向链表为空！");
    DuLNode<E> node = head;
    while (index > 0 && node.next != null) {
        node = node.next;
        index--;
    }
    return node;
}

　　可以通过指定元素来查找结点是否存在。

public DuLNode<E> getNodeByElem(E e) {
    if (isEmpty()) throw new ListException("双向链表为空！");
    DuLNode<E> node = head;
    while (node != null) {
        if (e.equals(node.data)) return node;
        node = node.next;
    }
    return null;
}

插入

　　双向链表的插入与单向链表一样，只不过在插入结点时除了设置next指针外，还要设置prior指针。

public void add(int index, E data) {
    DuLNode<E> node = new DuLNode<E>(data);
    if (index < 0) throw new ListException("位标不能为负！");
    if (head == null) {
        head = node;
    } else {
        // index == 0表示在前面插入结点
        if (index == 0) {
            node.next = head;
            head.prior = node;
            head = node;
        } else {
            DuLNode<E> n = getNode(index - 1);
            node.next = n.next;
            // n.next == null表示在后面插入结点，n.next != null表示在中间插入结点
            if (n.next != null) n.next.prior = node;
            n.next = node;
            node.prior = n;
        }
    }
}

删除

　　双向链表的删除也是在单向链表的基础上多一步对prior指针的设置。

public E remove(int index) {
    if (isEmpty()) return null;
    E e = null;
    if (head.next == null) {
        e = head.data;
        head = null;
    } else {
        if (index == 0) {
            e = head.data;
            head.next.prior = null;
            head = head.next;
        } else {
            DuLNode<E> node = getNode(index - 1);
            if (node.next != null) {
                node = node.next;
                e = node.data;
                node.next.prior = node.prior;
                node.prior.next = node.next;
            }
        }
    }
    return e;
}

双向循环链表

　　双向循环链表是第一个结点和最后一个结点相连的双向链表。双向循环链表最后一个结点的next指针指向第一个结点，第一个结点的prior指针指向最后一个结点。

　　

　　在双向循环链表中可以添加一个size变量来存储结点个数。

查找

　　双向循环链表可以通过循环查找指定位标的结点。指定位标可以通过对size求模来减少循环次数。

public DuLNode<E> getNode(int index) {
    if (index < 0) throw new ListException("位标不能为负！");
    if (isEmpty()) throw new ListException("链表为空！");
    index %= size;
    DuLNode<E> node = head;
    while (index > 0) {
        node = node.next;
        index--;
    }
    return node;
}

　　可以通过指定元素来查找结点是否存在。

public DuLNode<E> getNodeByElem(E e) {
    if (isEmpty()) throw new ListException("链表为空！");
    DuLNode<E> node = head;
    do {
        if (e.equals(node.data)) return node;
        node = node.next;
    } while (node != head);
    return null;
}

插入

　　双向循环链表的插入是在单向循环链表的基础上多一步对prior指针的设置。

public void add(int index, E data) {
    DuLNode<E> node = new DuLNode<E>(data);
    if (head == null) {
        node.prior = node.next = node;
        head = node;
    } else {
        index %= size;
        if (index == 0) {
            node.prior = head.prior;
            node.next = head;
            head.prior.next = node;
            head.prior = node;
            head = node;
        } else {
            DuLNode<E> n = getNode(index - 1);
            node.prior = n;
            node.next = n.next;
            n.next.prior = node;
            n.next = node;
        }
    }
    size++;
}

删除

　　双向循环链表的删除是在单向循环链表的基础上多一步对prior指针的设置。

public E remove(int index) {
    if (index < 0) throw new ListException("位标不能为负！");
    if (isEmpty()) return null;
    E e = null;
    if (size == 1) {
        e = head.data;
        head = null;
    } else {
        index %= size;
        if (index == 0) {
            e = head.data;
            head.next.prior = head.prior;
            head.prior.next = head.next;
            head = head.next;
        } else {
            DuLNode<E> node = getNode(index);
            e = node.data;
            node.next.prior = node.prior;
            node.prior.next = node.next;
        }
    }
    size--;
    return e;
}

约瑟夫问题

　　据说著名犹太历史学家约瑟夫有过这样一个故事：在罗马人占领乔塔帕特后，39个犹太人与约瑟夫及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式：41个人排成一个圆圈，由第1个人开始报数，每报到3的人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而约瑟夫和他的朋友并不想遵从，于是约瑟夫要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，最终逃过了这场死亡游戏。

　　这个故事演化来的问题就是著名的约瑟夫问题：由n个人围成一个圈，从1开始报数，报到m的人就出圈，由下一个人继续从1开始报数......求出出圈的人的顺序。

　　例如编号分别为1~5的5个小朋友围成一个圈，从1号小朋友开始报数，每次报到2的小朋友出圈：

　　a. 1号报1，2号报2，所以2号出圈。此时圈内剩下1-3-4-5。

　　b. 3号报1，4号报2，所以4号出圈。此时圈内剩下1-3-5。

　　c. 5号报1，1号报2，所以1号出圈。此时圈内剩下3-5。

　　d. 3号报1，5号报2，所以5号出圈。此时圈内剩下3。

　　综上所述，出圈的顺序为2-4-1-5-3。

解决方案

　　约瑟夫问题的特点是：

　　1. 所有人围成一个圈。也就是说，最后一个人的下一个人是第一个人。所以，可以使用单向环形链表来表示。

　　2. 从当前的人开始报数，报到m的人出圈。也就是说，出圈的人是当前的人之后的第m - 1个人。所以，如果假设当前人的编号为i，那么下一个出圈的人就是(i + m - 1) % size（i + m - 1可能大于size，所以需要通过对size求模），即删除(i + m - 1) % size结点。

　　所以，求解约瑟夫问题方法的定义如下：

/**
 * 求解约瑟夫问题
 * @param m  报到m的出圈
 * @return  按出圈的顺序排列的数组
 */
@SuppressWarnings("unchecked")
public static <E> E[] josephus(E[] datas, int m) {
    if (datas == null || datas.length == 0) throw new ListException("没有数据！");
    E[] result = (E[]) Array.newInstance(datas[0].getClass(), datas.length);
    CirLinkedList<E> l = new CirLinkedList<E>();
    l.addAll(datas);
    int i = 0;   // 从第一个人开始报数
    int j = 0;
    while (! l.isEmpty()) {
        i = (i + m - 1) % l.size();
        result[j++] = l.remove(i);
    }
    return result;
}

　　对该方法进行测试，输入人数n=5，报数m=2，输出结果为：

　　

　　可以看到该结果与原先分析得出的结果一致。

　　输入人数n=41，报数m=3，输出结果为：

　　

　　可以看到，结果的最后两个编号为16和31。这就是约瑟夫将朋友与自己安排在第16个与第31个位置，最终逃过了死亡游戏的原因。