深入理解链表和手写链表以及面试中常问链表的问题

用户3045442

发布于 2018-09-11 16:19:05

2.8K0

发布于 2018-09-11 16:19:05

文章被收录于专栏：Android研究院 Android研究院Android研究院

双链表

上一期讲到了顺序表与链表的基本知识了解链表的基本知识。并且分析了ArrayList的源码。顺序表(随机访问速度快，插入和删除效率低)和链表(随机访问速度慢，插入和删除效率高)的优缺点。在开始写双链表之前我们分析一下LinkedList(典型的双链表)源码，来看一下Java 中是如何实现双链表的。

LinkedList 源码解析

在分析一个类时，首先分析类的继承关系，再分析构造方法和属性。

LinkedList 继承关系

public class LinkedList extends AbstractSequentialList implements List, Deque, Cloneable, java.io.Serializable

LinkedList 继承 AbstractSequentialList,而 AbstractSequentialList extends AbstractList 在上一期中 ArrayList 继承AbstractList ，AbstractSequentialList 它实现了list 的一些位置相关的操作。
实现list 接口能对它进行队列操作。
Deque双端队列，双端队列中的元素可以从两端弹出，插入和删除操作限定在队列的两邊进行
Cloneable 覆盖了函数clone()
Serializable 支持序列化，能通过序列化传输数据

LinkedList 属性

关键字transient 标识的字段的生命周期仅存于调用者的内存中而不会写到磁盘里持久化。我们都知道一个对象只要实现了Serilizable接口，这个对象就可以被序列化，java的这种序列化模式为开发者提供了很多便利，我们可以不必关系具体序列化的过程，只要这个类实现了Seril izable接口，这个类的所有属性和方法都会自动序列化。然而在实际开发过程中，我们常常会遇到这样的问题，这个类的有些属性需要序列化，而其他属性不需要被序列化，打个比方，如果一个用户有一些敏感信息（如密码，银行卡号等），为了安全起见，不希望在网络操作（主要涉及到序列化操作，本地序列化缓存也适用）中被传输，这些信息对应的变量就可以加上transient关键字。换句话说，这个字段的生命周期仅存于调用者的内存中而不会写到磁盘里持久化。总之，java 的transient关键字为我们提供了便利，你只需要实现Serilizable接口，将不需要序列化的属性前添加关键字transient，序列化对象的时候，这个属性就不会序列化到指定的目的地中。

    transient int size = 0;
    /**
     * Pointer to first node.
     * Invariant: (first == null && last == null) ||
     *            (first.prev == null && first.item != null)
     */
    transient Node<E> first;
    /**
     * Pointer to last node.
     * Invariant: (first == null && last == null) ||
     *            (last.next == null && last.item != null)
     */
    transient Node<E> last;

每个节点都是存储对象Node，包括(E item;Node next;Node prev;)这就意味着LinkedList 占用的内存会比较大,ArrayList 只包括 E,LinkedList 比ArrayList 占用内存大

 private static class Node<E> {
        //当前节点的 item
        E item;
        //表示 当前节点的下一个节点
        Node<E> next;
        //表示 当前节点的上一个节点
        Node<E> prev;
        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }

LinkedList 构造方法

 /**
     * Constructs an empty list.
     */
    public LinkedList() {
    }
    /**
     * Constructs a list containing the elements of the specified
     * collection, in the order they are returned by the collection's
     * iterator.
     *
     * @param  c the collection whose elements are to be placed into this list
     * @throws NullPointerException if the specified collection is null
     */
    public LinkedList(Collection<? extends E> c) {
        this();
        addAll(c);
    }

LinkedList 有两个构造方法，第一个就不必说了，第二个构造一个链表，传入的是一个list(interface List extends Collection) addAll(c) 方法

 public boolean addAll(Collection<? extends E> c) {
        return addAll(size, c);
    }
  public boolean addAll(int index, Collection<? extends E> c) {
       //判断 index >= 0 && index <= size;
        checkPositionIndex(index);
        //将list 转换成一个数组 
        Object[] a = c.toArray();
        int numNew = a.length;
        //若数组的长度为0 返回false 不能构造链表
        if (numNew == 0)
            return false;
        Node<E> pred, succ;
        //若插入的位置 == 链表的大小
        if (index == size) {
            succ = null;
            //准备要插入的节点 == last 链表的最后一个节点，准备循环从最后一个节点添加
            pred = last;
        } else {
             //若插入的位置 ！= 链表的大小 找到要插入的位置
            succ = node(index);
            //准备插入的节点 == 插入位置的前一个节点
            pred = succ.prev;
        }
        //循环数组中的Object 创建Node 节点
        for (Object o : a) {
            @SuppressWarnings("unchecked") E e = (E) o;
            //创建新的节点Node
            Node<E> newNode = new Node<>(pred, e, null);
            //若准备插入的节点为null 说明 index == size 而 pred = last链表为空
            if (pred == null)
                first = newNode;
            else
                pred.next = newNode;
            pred = newNode;
        }
        //succ == null 说明 index == size
        if (succ == null) {
            last = pred;
        } else {
            pred.next = succ;
            succ.prev = pred;
        }
        size += numNew;
        modCount++;
        return true;
    }

LinkedList 添加节点

add(E e) 尾部插入 public boolean add(E e) { linkLast(e); return true; } /** * Links e as last element. */ void linkLast(E e) { //尾部节点 final Node<E> l = last; final Node<E> newNode = new Node<>(l, e, null); //尾部 == 新的节点 last = newNode; //注意判断尾部是否为空，若尾部last为空则说明链表为空 if (l == null) //第一个节点 == newNode first = newNode; else //之前的尾部节点的next 指向新添加的节点 l.next = newNode; //链表大小加一 size++; modCount++; }
add(int index, E element) 中间插入 public void add(int index, E element) { //插入的位置必须>=0 并且<= size checkPositionIndex(index); //尾部插入 if (index == size) linkLast(element); else //中间插入首先找到插入位置的节点 linkBefore(element, node(index)); } void linkBefore(E e, Node<E> succ) { // assert succ != null; //插入位置的节点的前一个节点 final Node<E> pred = succ.prev; //new 要插入的节点 final Node<E> newNode = new Node<>(pred, e, succ); succ.prev = newNode; if (pred == null) first = newNode; else pred.next = newNode; size++; modCount++; } Node<E> node(int index) { // assert isElementIndex(index); //插入的位置 < 链表大小的一半则从左侧 first 节点查找 if (index < (size >> 1)) { Node<E> x = first; for (int i = 0; i < index; i++) x = x.next; return x; } else { //插入的位置 > 链表大小的一半则从右侧 last 节点查找 Node<E> x = last; for (int i = size - 1; i > index; i--) x = x.prev; return x; } }

LinkedList 删除节点

public E remove(int index) {
        checkElementIndex(index);
        //要删除某个节点 同样要找到该位置的节点
        return unlink(node(index));
    }
E unlink(Node<E> x) {
        // assert x != null;
        final E element = x.item;
        final Node<E> next = x.next;
        final Node<E> prev = x.prev;
        //删除的节点前一个为空 则说明删除的是第一个节点
        if (prev == null) {
            //第一个节点first = 删除节点的下一个节点
            first = next;
        } else {
            //删除的节点前一个不为空 删除节点的前一个节点的next 
            //指向删除节点的下一个节点
            prev.next = next;
            //将删除节点 prev 置为null
            x.prev = null;
        }
        if (next == null) {
            last = prev;
        } else {
            next.prev = prev;
            x.next = null;
        }
        //将删除节点的item 置为null
        x.item = null;
        //链表减一
        size--;
        modCount++;
        return element;
    }

LinkedList 查找节点

查找节点为耗时较长，算法复杂度为 o(n) = n

  Node<E> node(int index) {
        // assert isElementIndex(index);
        //插入的位置 < 链表大小的一半 则从左侧  first 节点查找
        if (index < (size >> 1)) {
            Node<E> x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {
            //插入的位置 > 链表大小的一半则从右侧  last 节点查找
            Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }

链表总结

从上述分析我们可以得出，链表(LinkedList)的尾插效率高，中间插入和删除算法复杂度为 o (n) = n,对比顺序表（ArrayList ）插入删除都用到了复制System.arraycopy( elementData, index, elementData, index + 1,size - index); 算法复杂度要比双链表的插入和删除复杂度高。如果频繁的插入和删除操作建议用链表的存储结构；如果要想快速的查找到某条数据建议用顺序表的存储结构。

手写双链表

如何手写一个双链表，我们可以仿照LinkedList 的源码写一个简单的双链表

首先双链表的模型类：

class Node{
    Object data;
    Node next;
    Node per;
}

需要的属性

  int size;
  Node frist;
  Node last;

Node静态类

private static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;
        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }

完整的代码如下：

public class LinkedList<E> {
    public LinkedList() {
    }
    Node<E> frist;
    Node<E> last;
    int size;
    /**
     * 向链表的尾部添加一个元素
     *
     * @param e
     */
    public void add(E e) {
        linkLast(e);
    }
    public void add(int index, E e) {
        if (index < 0 || index > size) return;
        if (index == size) {//插入尾部
            linkLast(e);
        } else {
            Node<E> currentNode = node(index);//拿到当前位置要插入的节点
            Node<E> prev = currentNode.prev;
            Node<E> newNode = new Node<>(prev, e, currentNode);
            if (prev == null) {//头部插入
                frist = newNode;
            } else {//中间插入
                prev.next = newNode;//Note : 这里两个位置不能换
            }
            currentNode.prev = newNode;//Note: 查到的节点prev 要指向新的节点
            size++;
        }
    }
    public void remove(int index) {
        if (index < 0 || index > size) return;
        unLinkNode(node(index));
    }
    private void unLinkNode(Node<E> node) {
        Node<E> prev = node.prev;
        Node<E> next = node.next;
        if (prev == null){
            frist = next;
        }else {
            prev.next = next;
            node.prev = null;
        }
        if (next == null){
            last = prev;
        }else {
            next.prev = prev;
            node.next = null;
        }
        size --;
    }
    /**
     * 获取某个节点的元素
     *
     * @param index
     * @return
     */
    public E get(int index) {
        if (index < 0 || index > size) return null;
        return node(index).item;
    }
    private Node<E> node(int index) {
        if ((size >> 1) < index) {//从尾部开始循环
            Node<E> node = last;
            for (int i = size - 1; i > index; i--) {
                node = last.prev;
            }
            return node;
        } else {//从头部开始循环
            Node<E> node = frist;
            for (int i = 0; i < index; i++) {
                node = node.next;
            }
            return node;
        }
    }
    private void linkLast(E e) {
        Node<E> newNode = new Node<>(last, e, null);
        Node<E> l = last;//拿到之前的最后一个节点
        last = newNode;//将添加的新节点newNode 赋给last 最后一个节点
        if (l == null) {//如果之前的最后一个节点为空
            frist = newNode;
        } else {//如果之前的最后一个节点不为空
            l.next = newNode;
        }
        size++;
    }
    private static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;
        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }
}

知道如何写一个双链表，那么写一个单链表就更简单了。

在面试中经常问到，如何将一个单链表逆置?

在实现逆置之前我们写一个单链表，代码如下:

public class SingleList<E> {
    private static class Node<E> {
        E item;
        Node<E> next;
        public Node(E item, Node<E> next) {
            this.item = item;
            this.next = next;
        }
    }
    private Node<E> frist;
    private Node<E> last;
    public int size;
    /**
     * 向尾部添加一个元素
     *
     * @param e
     */
    public void add(E e) {
        lastList(e);
    }
    /**
     * 在某个位置插入一个元素
     *
     * @param e
     * @param index
     */
    public void add(E e, int index) {
        if (index < 0 || index > size) return;
        if (index == size) {//插入尾部
            lastList(e);
        } else {
            if (index == 0) {
                Node<E> l = frist;
                Node<E> newNode = new Node<>(e, l);//新的元素在插入位置的前一个位置
                frist = newNode;
            } else {
                Node<E> fNode = node(index - 1);//找到要插入位置的前一个位置
                Node<E> lNode = fNode.next;
                Node<E> newNode = new Node<>(e, lNode);
                fNode.next = newNode;
            }
            size++;
        }
    }
    /**
     * 删除某个节点
     *
     * @param index
     */
    public void remove(int index) {
        unLink(index);
    }
    private void unLink(int index) {
        if (index < 0 || index > size) return;
        if (index == size) {//删尾部
            Node<E> node = node(index - 1);
            node.next = null;
            last = node;
        } else if (index == 0) {//删头部
            Node<E> l = this.frist;
            frist = l.next;
        } else {
            Node<E> node = node(index - 1);//要删除的前一个节点
            Node<E> removeNode = node.next;//要删除的节点
            Node<E> lNode = removeNode.next;//要删除的后一个节点
            node.next = lNode;
        }
        size--;
    }
    public void remove(E e) {
        Node<E> newNode = frist;
        int index = -1;
        for (int i = 0; i < size; i++) {
            newNode = newNode.next;
            if (e.equals(newNode.item)) {
                index = i;
                break;
            }
        }
        if (index != -1)
            unLink(index);
    }
    private void lastList(E e) {
        Node<E> newNode = new Node<>(e, null);//一个新的节点
        Node<E> l = last;
        last = newNode;//将最后一个节点赋值
        if (l == null) {
            frist = newNode;
        } else {
            l.next = newNode;
        }
        size++;
    }
    /**
     * 获取节点的某个元素
     *
     * @param index
     * @return
     */
    public E get(int index) {
        if (index < 0 || index > size) {
            return null;
        }
        return node(index).item;
    }
    public Node<E> node(int index) {
        Node<E> newNode = frist;
        for (int i = 0; i < index; i++) {
            newNode = newNode.next;
        }
        return newNode;
    }
}

测试单链表的添加个删除

  SingleList<Integer> singleList = new SingleList<>();
        singleList.add(1);
        singleList.add(2);
        singleList.add(3);
        singleList.add(4);
        singleList.add(5);
//        singleList.add(9,0);
//        singleList.add(8,5);
//        singleList.add(7,2);
//        singleList.remove(6);
//        singleList.remove(3);
        for (int i = 0; i < singleList.size; i++) {
            System.out.print(singleList.get(i) + " ");
        }

如何实现逆置？

第一种方法，循环法

  /**
     * 单链表的逆置
     * 第一种方法实现 循环
     */
    public void inverse() {
        Node<E> l = this.last;
        Node<E> curr = this.frist;
        Node<E> reve = null;
        while (curr != null) {
            Node<E> temp = curr;
            curr = curr.next;
            temp.next = reve;
            reve = temp;
        }
        frist = reve;
    }

如上图所示：第一次循环后得到的 --》 temp = 1 curr =2 temp.next = null reve = temp = 1 ;链表的结构就变为 1 --> null 2 --> 3 --> 4. 第二次循环后得到的 --》 temp = 2 curr = 3 temp.next = 1 reve = temp = 2 ;链表的结构就变为 2 --> 1 --> null 3 --> 4 第三次循环后得到的 --》 temp = 3 curr = 4 temp.next = 2 reve = temp = 3 ;链表的结构就变为 3 --> 2 --> 1 --> null 4 …. 如此类推就可以得到一个逆置的单链表。

第二种方法，递归法

   /**
     * 递归的方式转置
     */
    public Node<T> reverse(Node<T> head) {
        if (head == null || head.next == null) {
            return head;
        }
        Node<T> tail = reverse(head.next);
        head.next.next = head;
        head.next = null;
        return tail;
    }
    public void transterReverse() {
        this.frist = reverse(this.frist);
    }

如上图所示递归法的逆置逻辑： 1 --> 2 --> 3 <-- 4

1 --> 2 <-- 3 <--4

1 <-- 2 <-- 3 <--4

至此，数据结构线性表的内容基本讲完。

本文参与腾讯云自媒体分享计划，分享自微信公众号。

原始发表：2018-02-04，如有侵权请联系 cloudcommunity@tencent.com 删除

其他

本文分享自 Android研究院微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

其他

登录后参与评论

0 条评论

热度