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

双链表

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

LinkedList 源码解析

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

LinkedList 继承关系

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

  1. LinkedList 继承 AbstractSequentialList,而 AbstractSequentialList extends AbstractList 在上一期中 ArrayList 继承AbstractList ,AbstractSequentialList 它实现了list 的一些位置相关的操作。
  2. 实现list 接口能对它进行队列操作。
  3. Deque双端队列,双端队列中的元素可以从两端弹出,插入和删除操作限定在队列的两邊进行
  4. Cloneable 覆盖了函数clone()
  5. 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 添加节点
  1. 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++; }
  2. 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

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

原文发布于微信公众号 - Android研究院(androidlinksu)

原文发表时间:2018-02-04

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏格子的个人博客

Java源码阅读之LinkedList - JDK1.8

前文基于缓冲数组的ArrayList已经分析过,那么同样作为List实现的LinkedList又有什么不一样呢?

1002
来自专栏Danny的专栏

探秘static——类不需实例化就能用?

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/huyuyang6688/article/...

1064
来自专栏Bingo的深度学习杂货店

Q67 Add Binary

Given two binary strings, return their sum (also a binary string). For example, ...

2858
来自专栏来自地球男人的部落格

[LeetCode] 442. Find All Duplicates in an Array

【原题】 Given an array of integers, 1 ≤ a[i] ≤ n (n = size of array), some elemen...

2098
来自专栏Android知识点总结

01--图解数据结构之数组实现集合

1334
来自专栏皮皮之路

【JDK1.8】JDK1.8集合源码阅读——LinkedList

32212
来自专栏浪淘沙

关于栈的几个小算法

    想法就是创建一个index变量,index指向含有值得下一个数组空间(假设数组中有两个值,index指向2)

1007
来自专栏LanceToBigData

Java集合源码分析(二)Linkedlist

前言   前面一篇我们分析了ArrayList的源码,这一篇分享的是LinkedList。我们都知道它的底层是由链表实现的,所以我们要明白什么是链表? 一、Li...

2787
来自专栏我的技术专栏

数据结构图文解析之:数组、单链表、双链表介绍及C++模板实现

2043
来自专栏皮皮之路

【JDK1.8】JDK1.8集合源码阅读——LinkedList

1443

扫码关注云+社区

领取腾讯云代金券