乐趣区

关于链表:结构与算法03单向链表和双向链表

本文源码:GitHub·点这里 || GitEE·点这里

一、链表简介

1、链表概念

链表是一种物理存储单元上非间断、非程序的存储构造,数据元素的逻辑程序是通过链表中的指针链接秩序实现的。链表由一系列节点组成,节点能够在运行时动静生成,节点包含两个局部:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域。

2、根底特点

内存存储

逻辑构造

特点形容

  • 物理存储上是无序且不间断的;
  • 链表是由多个节点以链式构造组成;
  • 逻辑层面上看造成一个有序的链路构造;

链表构造解决数组存储须要事后晓得元素个数的缺点,能够充分利用内存空间,实现灵便的内存动静治理。

二、单向链表

1、根底形容

单向链表是链表的一种,其特点是链表的链接方向是单向的,链表的遍历要从头部开始程序读取;结点形成,head 指针指向第一个成为表头结点,终止于最初一个指向 NULL 的指针。

2、根底操作

增加数据

  • 初始化 head 节点,作为链表的头;
  • 批改以后开端节点的 next 指针;
  • 新增加的节点房子在链表开端;

删除数据

遍历找到要删除的节点,把删除节点前个节点的指针指向该删除节点的下个节点;

三、双向链表

1、概念形容

双向链表也叫双链表,是链表的一种,链表的每个数据结点中都有两个指针,别离指向间接后继和间接前驱,从双向链表中的任意一个结点开始,都能够很疾速地拜访它的前驱结点和后继结点,链表构造的应用少数都是结构双向循环链表。

2、根底操作

增加数据

  • 遍历找到链表的最初一个节点;
  • 批改以后开端节点的 next 指针;
  • 新增加的节点房子在链表开端;
  • 增加最新尾节点的 prev 指针;

删除数据

  • 双向链表,基于要删除节点操作即可;
  • 操作上图中要删除的 Node2 节点;
  • Node2.prev.next = Node2.next;
  • Node2.next.prev = Node2.prev;

通过上述流程的操作,就把链表中一个节点删除,剩下节点再度连接成链式构造。

3、源码剖析

在 Java 的 API 中,LinkedList 是典型的双向链表构造,上面基于 LinkedList 源码看双向链表的操作。

根底案例

public class M01_Linked {public static void main(String[] args) {List<User> userList = new LinkedList<>() ;
        User removeUser = new User(200,"Second") ;
        // 增加元素
        userList.add(new User(100,"First")) ;
        userList.add(removeUser) ;
        userList.add(new User(300,"Third")) ;
        System.out.println("初始化:"+userList);
        // 批改元素
        userList.get(0).setUserName("Zero");
        System.out.println("批改后:"+userList);
        // 删除元素
        userList.remove(removeUser) ;
        System.out.println("删除后:"+userList);
    }
}
class User {
    private Integer userId ;
    private String userName ;
    public User(Integer userId, String userName) {
        this.userId = userId;
        this.userName = userName;
    }
    @Override
    public String toString() {
        return "User{" +
                "userId=" + userId +
                ", userName='" + userName + '\'' +
                '}';
    }
    // 省略 Get 和 Set 办法
}

节点形容

节点三个外围形容:数据,next 指针,prev 指针。

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;
    }
}

首位节点解决

基于 LinkedList 源码,首尾节点形式,针对上图双链表的首位指针特点,这里源码很好了解。

public class LinkedList {
    transient Node<E> first;
    transient Node<E> last;
    // 解决首节点
    private void linkFirst(E e) {
        final Node<E> f = first;
        final Node<E> newNode = new Node<>(null, e, f);
        first = newNode;
        if (f == null)
            last = newNode;
        else
            f.prev = newNode;
    }
    // 解决尾节点
    void linkLast(E e) {
        final Node<E> l = last;
        final Node<E> newNode = new Node<>(l, e, null);
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
    }
}

增加节点

增加节点的办法间接调用 linkLast 办法,把新节点放到链表的尾部即可。

public boolean add(E e) {linkLast(e);
    return true;
}

删除节点

第一步:遍历比照,找到要删除的节点;

public boolean remove(Object o) {if (o == null) {for (Node<E> x = first; x != null; x = x.next) {if (x.item == null) {unlink(x);
                return true;
            }
        }
    } else {for (Node<E> x = first; x != null; x = x.next) {if (o.equals(x.item)) {unlink(x);
                return true;
            }
        }
    }
    return false;
}

第二步:移除节点,从新搭建链表构造,并且把以后链表的数据置为 null,并返回被移除的节点;

E unlink(Node<E> x) {
    final E element = x.item;
    final Node<E> next = x.next;
    final Node<E> prev = x.prev;
    if (prev == null) {first = next;} else {
        prev.next = next;
        x.prev = null;
    }
    if (next == null) {last = prev;} else {
        next.prev = prev;
        x.next = null;
    }
    x.item = null;
    return element;
}

如上就是对 Java 中 LinkedList 双链表源码的局部构造剖析,这种代码看多了,总感觉本人写的代码不是 Java。

四、环形链表

在单链表中,将终端结点的指针域 NULL 改为指向表头结点或开始结点,这样就造成了环形链表:

环形链表链表的一种构造,特点是表中最初一个结点的指针域指向头结点,整个链表造成一个环。

五、源代码地址

GitHub·地址
https://github.com/cicadasmile/model-arithmetic-parent
GitEE·地址
https://gitee.com/cicadasmile/model-arithmetic-parent

举荐浏览:算法与数据结构

文章题目
构造与算法:稠密数组和二维数组转换
构造与算法:队列和栈构造
算法利用:RSA 算法,加密解密,签名验签流程详解
算法利用:递归算法,解决树形构造下的业务数据
退出移动版