面试官让我手写一个双向链表
笔者之前参加过一场视频面试,其中一个问题是说说ArrayList、LinkedList的区别,参加过面试的同学可能经常会被问到这个问题,当我说到ArrayList是基于数组实现的LinkedList是基于双向链表实现的时候,面试官说那你能写一个双向链表吗?
因为面试邀请邮件中告知面试时需要写代码,笔者在面试之前虽然看了一些数据结构方面的知识点,但当真正手写的时候还是费了一番功夫。趁着这次周末有空,写一篇文章总结下双向链表。
在前面的文章单链表的CRUD中详细介绍过单链表的插入、查找、修改和删除操作。我们可以发现单链表的查找方向只能是一个方向,从一个结点只能向后遍历,无法向前遍历,为克服单链表的这种单向性的缺点,我们可以利用双向链表。顾名思义,双向链表的结点中有两个指针域,next指针域指向后一个结点,prev指针域指向前一个结点。
学习双向链表的时候,不能孤立的学,我们可以与单向链表对比着学习。
单向链表
双向链表
Java中双向链表结点Node的表示
private static class Node {
private Integer item;
private Node next;
private Node prev;
public Node() {
}
public Node(Integer item, Node next) {
this.item = item;
this.next = next;
}
}
双向链表的查找、修改操作与单向链表一致,但在插入和删除时有很大的不同,在双向链表中插入和删除需要同时修改两个方向的指针,下面分别介绍双向链表的插入和删除操作。
双向链表的插入
双向链表的插入操作,一般是尾部插入。首先要根据头结点找到尾结点,这个过程与单向链表的操作类似,根据头结点依次向后遍历找到尾结点,将尾结点的next指针域指向新结点。不同的是需要将新结点的prev指针域指向尾结点。
/**
* 在链表尾部插入元素
* @param item
* @return
*/
public boolean add(Integer item) {
Node newNode = new Node(item, null);
// tmp 指向头结点
Node tmp = head;
// 找到尾结点
while (tmp.next != null) {
tmp = tmp.next;
}
tmp.next = newNode;
newNode.prev = tmp;
return true;
}
双向链表的删除
删除指定索引位置上的结点,单向链表需要找到待删除结点的前一个结点。将前一个结点的next指针域指向待删除结点的后一个结点。可以发现单向链表不能实现自删除,双向链表可以实现自删除。
在双向链表中,比如我们要删除b结点,首先根据head结点依次向后遍历找到待删除的结点b,通过b结点的prev指针域可以定位到它的前一个结点a,通过b结点的next指针域可以定位到它的后一个结点c。然后将a结点的next指针域指向c,同时将c结点的prev指针域指向a。
/**
* 删除指定索引位置的结点
* @param index
* @return
*/
public Integer remove(int index) {
this.checkIndex(index);
// 找到要删除的结点
Node node = this.node(index);
Integer val = node.item;
node.item = null;
// 删除自身
node.prev.next = node.next;
if(node.next != null) {
node.next.prev = node.prev;
}
node.next = null;
node.prev = null;
return val;
}
Node node(int index) {
Node tmp = head;
for(int i = 0; i <= index; i++) {
tmp = tmp.next;
}
return tmp;
}
完整代码如下:
public class DoubleLinkedList {
// 头结点
private Node head;
// 链表中实际元素个数
private int size;
public DoubleLinkedList() {
this.head = new Node();
this.size = 0;
}
/**
* 在链表尾部插入元素
* @param item
* @return
*/
public boolean add(Integer item) {
Node newNode = new Node(item, null);
// tmp 指向头结点
Node tmp = head;
// 找到尾结点
while (tmp.next != null) {
tmp = tmp.next;
}
tmp.next = newNode;
newNode.prev = tmp;
size++;
return true;
}
/**
* 返回指定位置的元素
* @param index
* @return
*/
public Integer get(int index) {
this.checkIndex(index);
Node node = this.node(index);
return node.item;
}
/**
* 删除指定索引位置的结点
* @param index
* @return
*/
public Integer remove(int index) {
this.checkIndex(index);
// 找到要删除的结点
Node node = this.node(index);
Integer val = node.item;
node.item = null;
// 删除自身
node.prev.next = node.next;
if(node.next != null) {
node.next.prev = node.prev;
}
node.next = null;
node.prev = null;
size--;
return val;
}
/**
* 遍历元素
*/
public void list() {
Node tmp = head;
while(tmp.next != null) {
tmp = tmp.next;
System.out.println(tmp.item);
}
}
Node node(int index) {
Node tmp = head;
for(int i = 0; i <= index; i++) {
tmp = tmp.next;
}
return tmp;
}
private void checkIndex(int index) {
if(index < 0 || index >= size) {
throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);
}
}
private static class Node {
private Integer item;
private Node next;
private Node prev;
public Node() {
}
public Node(Integer item, Node next) {
this.item = item;
this.next = next;
}
}
}
与单向链表相比,双向链表可以向前或向后查找,双向链表可以自我删除。
「更多精彩内容请关注公众号geekymv,喜欢请分享给更多的朋友哦」
推荐阅读
-
腾讯面试官问我Java中boolean类型占用多少个字节?我说一个,面试官让我回家等通知
-
今天去面试 面试官给我出了一个老鼠走迷宫的问题 让我把程序写出来,面试官走迷宫
-
腾讯面试官问我Java中boolean类型占用多少个字节?我说一个,面试官让我回家等通知
-
今天去面试 面试官给小弟我出了一个老鼠走迷宫的有关问题 让小弟我把程序写出来
-
今天去面试 面试官给我出了一个老鼠走迷宫的问题 让我把程序写出来,面试官走迷宫_PHP教程
-
今天去面试 面试官给我出了一个老鼠走迷宫的问题 让我把程序写出来,面试官走迷宫
-
今天去面试 面试官给我出了一个老鼠走迷宫的问题 让我把程序写出来,面试官走迷宫_PHP教程
-
面试官让我手写一个读写锁出来,我...
-
面试官让我手写一个双向链表
-
腾讯面试官问我Java中boolean类型占用多少个字节?我说一个,面试官让我回家等通知...