美文网首页
数据结构——链表

数据结构——链表

作者: 柏丘君 | 来源:发表于2018-02-09 21:37 被阅读0次

    链表也是一种常见的数据结构，从数据结构类型上区分，链表属于存储结构的一种：链式存储结构。
    和顺序存储结构一样，链式存储结构也可以用来作为实现其他数据结构的基础，比如前面介绍的线性表、栈、队列等。

    顺序存储结构和链式存储结构的区别

    使用顺序存储结构存放数据时，使用的是内存空间中连续的内存，如下图所示：


    连续内存空间

    使用顺序存储结构时，数据需要存放在连续的内存空间中。这种存储结构的优点在于读取速度很快，缺点在于无法有效利用内存空间。怎么理解呢？举个例子，如果只使用顺序存储结构，在程序的运行过程中，会产生很多的临时变量，这些变量在不用时会被垃圾回收，当变量被回收后，内存中就出现了不连续的情况，也可以叫做内存空洞。如下图所示，黑色区域表示内存空洞：


    内存空洞
    随着程序的运行，这样的内存空洞会越来越多，此时如果程序中需要用到较大的内存空间，而剩余的连续内存不够的情况下，将无法成功分配内存，但内存中又有很多的内存空洞，却无法得到有效利用。
    要解决这个问题，有两个解决方案：
    1. 将内存空洞后面的数据往前移
      第一种方式就是每隔一段时间，将内存空洞后面的数据向前移，以达到“挤压”内存空洞的目的。这种方式的缺点在于性能浪费严重。

    2. 使用链式存储结构
      第二种方式就是使用链式存储结构：在某些内存空洞中存放一部分数据，再存放下一块可用内存空洞的地址，通过地址把这些可用的内存空洞连接起来，实现一个链式的结构，这就是链表。下面是链表的基本结构：


      链表

      上图展示了链表的基本结构，对于链表，其中的每个元素我们称之为节点。可见每个节点至少需要包含两部分内容：

    • 数据区：用来存放数据
    • 地址区：用来存放下一个节点的地址

    链表的分类

    通常我们说的链表也叫作单向链表，此外，链表还有两个常用的衍生结构：双向链表和循环链表。本文主要介绍单向链表的实现，双向链表和循环链表在后文介绍。

    链表的代码实现

    下面是链表的代码实现，首先来定义一个 ISingleNode 接口和 SingleNode 类，用来实现链表中的节点。

    节点类和接口的代码实现

    interface ISingleNode<T>{
    // 数据区
    data:T;
    // 地址区
    next:ISingleNode<T>;
}

class SingleNode<T> implements ISingleNode<T>{
    data:T = null;
    next:ISingleNode<T> = null;
    constructor(data?:T){
        this.data = data;
    }
}

    链表类的接口和代码实现

    首先定义 ISingleLinkedList 接口，规范链表类中的基本操作方法：

    interface ISingleLinkedList<T>{
    // 获取链表的长度
    size():number;
    // 获取链表头
    head():ISingleNode<T>;
    // 增加节点
    append(item:T):ISingleNode<T>;
    // 删除节点
    remove(item:T):void;
    // 根据位置删除
    removeAt(pos:number):void;
    // 插入节点
    insert(newItem:T,oldItem:T):ISingleNode<T>;
    // 在具体的位置插入
    insertAt(newItem:T,pos:number):ISingleNode<T>;
    // 清空链表
    clear():void;
    // 判断链表是否为空
    isEmpty():boolean;
    // 查找节点和其前驱
    find(item:T):{
        previous:ISingleNode<T>,
        current:ISingleNode<T>,
        currentPos:number,
        previousPos:number
    };
    // 根据位置查找节点和其前驱
    findAt(pos:number):{
        previous:ISingleNode<T>,
        current:ISingleNode<T>,
        currentPos:number,
        previousPos:number
    };
    // 获取链表中的元素
    toString():ISingleNode<T>[];
}

    定义链表类 SingleLinkedList：

    class SingleLinkedList<T> implements ISingleLinkedList<T>{
    private _size:number = 0;
    private _head:ISingleNode<T> = new SingleNode();
}

    下面逐个讲解链表类中的几个关键方法。

    1. 实现 find() 方法
      首先需要实现 find() 方法，该方法用来从链表中查找节点，以供后面的添加和删除方法使用。
    find(item:T):{
    previous:ISingleNode<T>,
    current:ISingleNode<T>,
    currentPos:number,
    previousPos:number,
}{
    if(!item){
        throw new Error("参数错误!")
    }
    let 
        previous:ISingleNode<T> = null,
        current:ISingleNode<T> = this._head,
        index:number = -1;
    while(current){
        // 更新索引值
        index++;
        // 判断当前节点中的数据和传入的是否匹配
        if(current.data === item){
            break;
        }
        // 将 current 赋值给 previous
        // 将 current.next 赋值给 current
        // 在下一次迭代中使用
        previous = current;
        current = current.next;
    }

    // HACK 在前面的循环中找不到对于的元素时,会获取到尾节点
    // 这里进行一次二次验证
    if(current.data !== item){
        index = -1;
    }

    // 处理未找到的情况
    if(index === -1){
        return{
            previous:null,
            current:null,
            previousPos:-1,
            currentPos:-1
        }
    }
    return{
        previous,
        current,
        currentPos:index,
        // 前驱的位置在当前节点之前
        previousPos:index - 1
    }
}

    这个方法（和配套的 findAt()）是链表类中核心方法，再进行链表的添加、插入或删除操作时，首先需要查找链表中的某个节点和其前驱节点，查找总是从链表的头部开始的。

    1. 实现 append() 方法
      该方法用来向链表中添加节点，在添加时有两种情况：
    • 链表为空时，将头节点替换为新节点
    • 链表不为空时，将尾结点替换为新节点
    append(item:T):ISingleNode<T>{
    const newNode = new SingleNode<T>(item);
    // 链表中没有节点
    if(!this._size){
        this._head = newNode;
    }else{
        const {current} = this.findAt(this._size - 1);
        current.next = newNode
    }
    this._size++;
    return newNode;
}

    3.实现 insert() 方法
    该方法用来向链表中插入元素，也有两种情况：

    • 插入的位置是头节点，将头节点替换为新节点
    • 插入的位置是其他节点，将原始节点的位置插入新节点，同时将原始节点向后移，这时就需要用到原始节点的前驱节点
    insert(newItem:T,oldItem:T):ISingleNode<T>{
    // 创建新节点
    const newNode = new SingleNode(newItem);
    // 查找旧节点及其前驱节点
    const {current,previous} = this.find(oldItem);
    // 没有查找到旧节点,直接返回
    if(!current) return null;
    // 当 previous 为 null 时,说明是头节点
    if(!previous){
        newNode.next = current;
        this._head = newNode;
    }else{
        // 将新建节点的 next 指向旧节点
        newNode.next = current;
        // 将旧节点前驱的 next 指向新建的节点
        previous.next = newNode;
    }
    this._size++;
    return newNode;
}
    1. 实现 remove() 方法
      该方法用来从链表中移除节点。
    remove(item:T):void{
    // 获取当前节点和其的前驱
    let { current,previous } = this.find(item);
    // 还没有添加节点的情况
    if(!current) return;
    // 没有前驱节点，说明是头节点
    if(!previous){
        this._head = current.next;
    }else{
        // 将当前节点的前驱的 next 指向当前节点的后继
        previous.next = current.next;
    }
    // 移除当前节点
    current = null;
    // 更新链表长度
    this._size--;
}

    下面是 SingleLinkedList 类的完整代码实现：

    class SingleLinkedList<T> implements ISingleLinkedList<T>{
    private _size:number = 0;
    private _head:ISingleNode<T> = new SingleNode();
    size():number{
        return this._size;
    }
    head():ISingleNode<T>{
        return this._head;
    }
    clear():void{
        this._head = null;
        this._head = new SingleNode();
        this._size = 0;
    }
    isEmpty():boolean{
        return !this._size;
    }
    append(item:T):ISingleNode<T>{
        const newNode = new SingleNode<T>(item);
        // 链表中没有节点
        if(!this._size){
            this._head = newNode;
        }else{
            const {current} = this.findAt(this._size - 1);
            current.next = newNode
        }
        this._size++;
        return newNode;
    }
    find(item:T):{
        previous:ISingleNode<T>,
        current:ISingleNode<T>,
        currentPos:number,
        previousPos:number,
    }{
        if(!item){
            throw new Error("参数错误!")
        }
        let 
            previous:ISingleNode<T> = null,
            current:ISingleNode<T> = this._head,
            index:number = -1;
        while(current){
            // 更新索引值
            index++;
            // 判断当前节点中的数据和传入的是否匹配
            if(current.data === item){
                break;
            }
            // 将 current 赋值给 previous
            // 将 current.next 赋值给 current
            // 在下一次迭代中使用
            previous = current;
            current = current.next;
        }

        // HACK 在前面的循环中找不到对于的元素时,会获取到尾节点
        // 这里进行一次二次验证
        if(current.data !== item){
            index = -1;
        }

        // 处理未找到的情况
        if(index === -1){
            return{
                previous:null,
                current:null,
                previousPos:-1,
                currentPos:-1
            }
        }
        return{
            previous,
            current,
            currentPos:index,
            // 前驱的位置在当前节点之前
            previousPos:index - 1
        }
    }
    findAt(pos:number):{
        previous:ISingleNode<T>,
        current:ISingleNode<T>,
        currentPos:number,
        previousPos:number,
    }{
        let 
            previous:ISingleNode<T> = null,
            current:ISingleNode<T> = this._head,
            index:number = -1;
            
        if(pos < 0 || pos > this._size - 1){
            throw  new Error("索引越界！");
        }

        while(current){
            index++;
            if(index === pos){
                break;
            }
            previous = current;
            current = current.next;
        }

        // 处理未找到的情况
        if(index === -1){
            return{
                previous:null,
                current:null,
                previousPos:-1,
                currentPos:-1
            }
        }
        return{
            previous,
            current,
            currentPos:index,
            // 前驱的位置在当前节点之前
            previousPos:index - 1
        }
    }
    remove(item:T):void{
        // 获取当前节点和其的前驱
        let { current,previous } = this.find(item);
        // 还没有添加节点的情况
        if(!current) return;
        // 没有前驱节点，说明是头节点
        if(!previous){
            this._head = current.next;
        }else{
            // 将当前节点的前驱的 next 指向当前节点的后继
            previous.next = current.next;
        }
        // 移除当前节点
        current = null;
        // 更新链表长度
        this._size--;
    }    
    removeAt(pos:number):void{
        // 获取当前节点和其的前驱
        let { current,previous } = this.findAt(pos);
        // 还没有添加节点的情况
        if(!current) return;
        // 没有前驱节点，说明是头节点
        if(!previous){
            this._head = current.next;
        }else{
            // 将当前节点的前驱的 next 指向当前节点的后继
            previous.next = current.next;
        }
        // 移除当前节点
        current = null;
        // 更新链表长度
        this._size--;
    }
    insert(newItem:T,oldItem:T):ISingleNode<T>{
        // 创建新节点
        const newNode = new SingleNode(newItem);
        // 查找旧节点及其前驱节点
        const {current,previous} = this.find(oldItem);
        // 没有查找到旧节点,直接返回
        if(!current) return null;
        // 当 previous 为 null 时,说明是头节点
        if(!previous){
            newNode.next = current;
            this._head = newNode;
        }else{
            // 将新建节点的 next 指向旧节点
            newNode.next = current;
            // 将旧节点前驱的 next 指向新建的节点
            previous.next = newNode;
        }
        this._size++;
        return newNode;
    }
    insertAt(newItem:T,pos:number):ISingleNode<T>{
        // 创建新节点
        const newNode = new SingleNode(newItem);
        // 查找旧节点及其前驱节点
        const {current,previous} = this.findAt(pos);
        if(!current) return null;
        // 当 previous 为 null 时,说明是头节点
        if(!previous){
            newNode.next = current;
            this._head = newNode;
        }else{
            // 将新建节点的 next 指向旧节点
            newNode.next = current;
            // 将旧节点前驱的 next 指向新建的节点
            previous.next = newNode;
        }
        this._size++;
        return newNode;
    }
    toString():ISingleNode<T>[]{
        const tmp:ISingleNode<T>[] = [];
        let current:ISingleNode<T> = this._head;
        while(current){
            tmp.push(current);
            current = current.next;
        }
        return tmp;
    }
}

    总结

    链表在实现上比前面几个数据结构要复杂一点，这是因为在实现链表的添加、插入和删除操作时还需要修复节点地址区的指向问题。通常，链表操作需要考虑两种情况：

    • 在头节点进行添加、插入和删除操作
    • 在其他位置进行添加、插入和删除操作

    当在头节点进行操作时，不需要使用头节点的前驱节点，因为链表的头节点没有前驱节点，只需要修正头节点的 next 属性，或者使用新的节点替换头节点。
    在其他位置进行操作时，需要使用到该节点的前驱节点，并修正前驱节点的 next 属性。同时，如果是删除操作，还需要使用到该节点的后继节点，在修正前驱节点和后继节点的地址区指向后，还需要将被删除的节点置为 null，防止内存泄露。

    完。

    相关文章

      网友评论

          本文标题：数据结构——链表

          本文链接：https://www.haomeiwen.com/subject/btqxtftx.html

          延伸阅读

          深度阅读

          • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

          栏目导航

          热点阅读

          关于我们|服务条款|联系我们|数据结构——链表|投稿指南|网站地图|RSS订阅|排版工具|手机版

          提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

          Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

          备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

          本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

          所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！