背景
这两天花了些时间研究了一道题目,把解题的思维过程记录一下。原题目如下:
实现一个双向链表的倒置功能(1->2->3 变成 3->2->1),请勿直接使用JDK的LinkedList。
解题
拆题
拿到这个题目后,第一感觉网上有这个题,当然,不能一上来就去搜答案,这类题旨在考验程序员的问题分析能力的,直接看了答案就没有意义了。先自己去想,实在有的点卡住了,再去搜索一些思路。而且也只去看资料中关于卡主这部分的内容,不要全篇看,以自己的思考为主。
然后我们开始分析。要想解题,首先要明白这个题是想让我们做什么。很明显,这个题包含了两个要点:
- 实现倒置(结果)
- 实现双向链表数据结构(结果依赖的前提)
实现倒置是结果,实现双向链表数据结构是依赖,那么我们从结果开始思考,将得出结果的逻辑抽象出来,然后再慢慢反推依赖。
纸笔分析
这类题有个特点,第一眼看上去会比较懵逼,生在脑子里想也比较累,所以我们可以在纸端辅助思考,用文字来捋顺自己的思路:
上图中是我的最初始的分析思路,当然,到后期编码实现时,会发现其中的step3其实是不全面的,没关系,在纸和笔分析阶段我们要写的是最直接的思路,后期会不断优化。
编码实现
在编码阶段,我是与思考阶段反着来的,我先实现了依赖,也就是先实现双向链表这个数据结构
那么,代码从哪里写起呢?我是从接口开始的,因为很明显,在JDK的标准库里,都是从接口开始的,接口对消费端提供了行为的定义。很明显,作为一个最基本的线性表应当有删增改查四个方法,然后对于双向的表来说,应当有getFirst和getLast,所以,最基本的两个接口就有了。
package com.github.since1986.learn.collection;
/**
* 线性表
*/
public interface List<E> {
void add(E element);
void add(int index, E element);
E get(int index);
void remove(E element);
void remove(int index);
int size();
}
package com.github.since1986.learn.collection;
/**
* 双向表
*/
public interface Deque<E> extends List<E> {
E getFirst();
E getLast();
}
然后我们的双向链表LinkedList
应当实现双向表Deque
public class LinkedList<E> implements Deque<E>
然后再思考,我应当怎样存储双线链表中的节点呢,在这里,我其实第一开始思路有点跑偏了,由于原来我看过JDK中的ArrayList
的代码,所以我总是想是不是用一个数组来存储,但是后来越想越觉得别扭,索性打开了JDK的LinkedList
的代码,看了一眼,恍然大悟,其实定义一个内部的类Node
,Node
中包含了指向next
和previous
的引用,这个引用本身就构成了一个链式的结构。OK了,数据结构搞定。
//核心数据结构(不对外包暴露)
static class Node<E> {
private Node<E> previous;
private Node<E> next;
E element;
Node(Node<E> previous, Node<E> next, E element) {
this.previous = previous;
this.next = next;
this.element = element;
}
}
注意一点,这个数据结构不应被LinkedList
的消费者看到,保持内聚性。
然后我们来实现add
,有了add
我们就能够添加测试数据了,其他有几个方法和题目无关,我们可以先放着不实现。
@Override
public void add(E element) {
if (size == 0) { //假如当前的size == 0,那么就让当前add进来的元素,生成节点成为first节点和last节点
first = last = new Node<>(null, null, element);
} else { //否则向last节点后添加一个新的节点(也就是生成一个新节点,将last节点的next指向这个新节点),让后让新的节点成为last就可以了
Node<E> newLast = new Node<>(last, null, element);
last.next = newLast;
last = newLast;
}
size++;
}
再来实现get
以及其依赖的getNode
private Node<E> getNode(int index) {
if (index < 0 || index > size - 1) {
throw new IndexOutOfBoundsException();
} else if (size == 0) { //如果当前size == 0则返回null
return null;
} else if (index < size / 2) { //如果index处于list的前半部分(也就是index < size / 2)那么就从first节点开始向后找
Node<E> temp = first;
for (int i = 0; i < index; i++) {
temp = temp.next;
}
return temp;
} else { //否则,从last节点开始向前找
Node<E> temp = last;
for (int i = size - 1; i > index; i--) {
temp = temp.previous;
}
return temp;
}
}
@Override
public E get(int index) {
return getNode(index) == null ? null : getNode(index).element;
}
到这里,基本的数据结构算是实现了,我们来看一眼完整的LinkedList
代码吧:
package com.github.since1986.learn.collection;
/**
* (双向)链表
*/
public class LinkedList<E> implements Deque<E> {
private int size;
private Node<E> first;
private Node<E> last;
@Override
public void add(E element) {
if (size == 0) { //假如当前的size == 0,那么就让当前add进来的元素,生成节点成为first节点和last节点
first = last = new Node<>(null, null, element);
} else { //否则向last节点后添加一个新的节点(也就是生成一个新节点,将last节点的next指向这个新节点),让后让新的节点成为last就可以了
Node<E> newLast = new Node<>(last, null, element);
last.next = newLast;
last = newLast;
}
size++;
}
@Override
public void add(int index, E element) {
//TODO 与题目无关,暂不实现
}
@Override
public E get(int index) {
return getNode(index) == null ? null : getNode(index).element;
}
@Override
public void remove(E element) {
//TODO 与题目无关,暂不实现
}
@Override
public void remove(int index) {
//TODO 与题目无关,暂不实现
}
@Override
public int size() {
return size;
}
@Override
public E getFirst() {
return getFirstNode().element;
}
@Override
public E getLast() {
return getLastNode().element;
}
//核心数据结构(不对外包暴露)
static class Node<E> {
private Node<E> previous;
private Node<E> next;
E element;
Node(Node<E> previous, Node<E> next, E element) {
this.previous = previous;
this.next = next;
this.element = element;
}
Node<E> getPrevious() {
return previous;
}
void setPrevious(Node<E> previous) {
this.previous = previous;
}
Node<E> getNext() {
return next;
}
void setNext(Node<E> next) {
this.next = next;
}
}
private Node<E> getNode(int index) {
if (index < 0 || index > size - 1) {
throw new IndexOutOfBoundsException();
} else if (size == 0) { //如果当前size == 0则返回null
return null;
} else if (index < size / 2) { //如果index处于list的前半部分(也就是index < size / 2)那么就从first节点开始向后找
Node<E> temp = first;
for (int i = 0; i < index; i++) {
temp = temp.next;
}
return temp;
} else { //否则,从last节点开始向前找
Node<E> temp = last;
for (int i = size - 1; i > index; i--) {
temp = temp.previous;
}
return temp;
}
}
Node<E> getFirstNode() {
return size == 0 ? null : getNode(0);
}
Node<E> getLastNode() {
return size == 0 ? null : getNode(size - 1);
}
void setFirstNode(Node<E> first) {
this.first = first;
}
void setLastNode(Node<E> last) {
this.last = last;
}
@Override
public String toString() {
StringBuilder stringBuilder = new StringBuilder();
stringBuilder.append("(null) <-> ");
Node<E> node = first;
while (node != null) {
stringBuilder.append(node.element);
stringBuilder.append(" <-> ");
node = node.next;
}
stringBuilder.append("(null)");
return stringBuilder.toString();
}
}
实现好了数据结构,我们再来实现算法倒置吧,这才是最终目标。这里注意一点,我们要实现的reverse
方法不应在LinkedList
中提供,因为在LinkedList
语义上,提供这个方法并无意义,reverse
更应该是个util
类的方法,输入的是一个LinkedList
,输出是倒置后的LinkedList
。所以我们把这个方法封装在一个工具类里面对消费者代码提供。由于我们的reverse
方法要访问LinkedList
内部的Node
类的API,而Node
类访问是包
级别的,所以我们的工具类应当同LinkedList
在同一个包下定义。
来看具体代码吧,算法实现的思路写在注释里了:
package com.github.since1986.learn.collection;
public final class LinkedListUtils {
/*
* 倒置(根据高内聚的原则,这个API不应由LinkedList本身提供,因为倒置是要操作LinkedList内部API Node的,这个Node对消费者应当是不可见的,所以用了一个与LinkedList同一个包的Utils类来操作,这样就对外掩藏了Node这个API)
* 分为两个步骤:
* 第一步 交换每个节点的previous和next
* 第二步 交换LinkedList的first和last
*/
public static <E> LinkedList<E> reverse(LinkedList<E> linkedList) {
//保存原首尾节点信息,用于交换每个节点的previous和next后将LinkedList的first和last进行交换
LinkedList.Node<E> originalFirstNode = linkedList.getFirstNode();
LinkedList.Node<E> originalLastNode = linkedList.getLastNode();
//交换每个节点的previous和next
LinkedList.Node<E> originalOrderCurrentNode = originalFirstNode; //按照原顺序循环
while (originalOrderCurrentNode != null) { //按照原LinkedList的顺序循环,直至到达null(假如原LinkedList为 (null) <-> 1 <-> 2 <-> 3 <-> 4 <-> (null) 那么也就是按 1 -> 2 -> 3 -> 4 -> (null) 这样来循环,其中4后面的(null)为循环终止条件)
LinkedList.Node<E> originalPrevious = originalOrderCurrentNode.getPrevious(); //获得当前node的原previous
LinkedList.Node<E> originalNext = originalOrderCurrentNode.getNext(); //获得当前node的原next
LinkedList.Node<E> tempReference = originalOrderCurrentNode; //新建一个引用,后续的previous和next的交换在新引用上进行,不影响原LinkedList的节点,这样才能让while循环能够继续(可以想象一下,如果直接在原节点上交换,假如当前由1节点循环到了2个节点 那么 1 -> 2 -> 3交换后就变成了 3 -> 2 -> 1 ,循环的下一次等于还是1,就重复了,就不是原顺序在循环了,逻辑上是不对的)
originalOrderCurrentNode = originalNext; //让循环继续到下一节点
tempReference.setPrevious(originalNext); //将当前node的previous设置为原来的next
tempReference.setNext(originalPrevious); //将当前node的next设置为原来的previous
}
//交换LinkedList的first和last
linkedList.setFirstNode(originalLastNode);
linkedList.setLastNode(originalFirstNode);
return linkedList;
}
}
在实现倒置时,我在怎样让while循环能够继续这里卡住了,怎么想也想不通,后来看了看这篇文章中这段代码:
public DListNode reverse(DListNode head) {
DListNode curr = null;
while (head != null) {
curr = head;
head = curr.next;
curr.next = curr.prev;
curr.prev = head;
}
return curr;
}
才明白了,其实用一个中间引用就好了。另外在前面纸笔分析处我们提到了,纸笔分析中的step3并不全面,其实是少了:
//交换LinkedList的first和last
linkedList.setFirstNode(originalLastNode);
linkedList.setLastNode(originalFirstNode);
这一环节,没有这一环节倒置后每个Node虽然是正确的,但是首尾节点并不正确,后来我才想明白,实际上首尾对调后才算完成了整个链表的倒置。
好,到了这里,基本上题目就解完了。整体工程在我的GitHub里。
总结
通过这个题目,锻炼了一下自己思考/分析/解决问题的能力,同时也对JDK中的LinkedList
加深了理解.
参考资料
Java标准库的LinkedList
源码
Linked List - 链表