欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

面试官让我手写一个双向链表

程序员文章站 2022-04-07 21:53:47
...

笔者之前参加过一场视频面试,其中一个问题是说说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,喜欢请分享给更多的朋友哦」
面试官让我手写一个双向链表