链表

作者: 林键燃 | 来源:发表于2019-03-08 15:36 被阅读0次

内容

  • 链表数据结构
  • 向链表添加元素
  • 从链表移除元素
  • 使用 LinkedList 表
  • 双向链表
  • 循环链表

链表数据结构

链表存储有序的元素集合,链表中的元素在内存中不是连续放置的。每个元素由一个存储元素本身的节点和一个指向下一个元素的引用(也称指针或链接)组成

实现

单向链表

class Node {
    constructor(element) {
        this.element = element
        this.next = null
    }
}

class LinkedList {
    constructor() {
        this.length = 0
        this.head = null
    }
    append(element) {
        let node = new Node(element)
        let current = null

        if (this.length === 0) {
            this.head = node
        } else {
            current = head

            while (current.next) {
                current = current.next
            }

            current.next = node
        }
        this.length++
    }
    insert(position, element) {
        if (position < 0 || position > this.length) {
            return false
        }

        let index = 0,
            previous = null,
            current = this.head,
            node = new Node(element)
        
        if (position === 0) {
            node.next = current
            this.head = node
        } else {
            while (index++ < position) {
                previous = current
                current = current.next
            }
            node.next = current
            previous.next = node
        }
        this.length++

        return true      
    }
    removeAt(position) {
        if (position < 0 || position > this.length) {
            return null
        }

        let index = 0,
            previous = null,
            current = this.head
        
        if (position === 0) {
            this.head = current.next
        } else {
            while (index++ < position) {
                previous = current
                current = current.next
            }
            previous.next = current.next
        }
        this.length--
        return current.element
    }
    remove(element) {
        let index = this.indexOf(element)
        return this.removeAt(index)
    }
    indexOf(element) {
        let index = 0,
            current = this.head
        
        while (current) {
            if (element === current.element) {
                return index
            }
            index++
            current = current.next
        }

        return -1
    }
    isEmpty() {
        return this.length === 0
    }
    size() {
        return this.length
    }
    getHead() {
        return head
    }
    toString() {
        let string = '',
            current = this.head
        
        while (current) {
            string += current.element + (current.next ? ',' : '')
            current = current.next
        }
        return string
    }
}

双向链表

相关文章

  • 链表基础

    链表基础 链表长度 链表为空 链表结构 链表增加

  • 双向链表&双向循环链表

    链表分为:单链表、单向循环链表、双向链表、双向循环链表本节主要说明:双向链表、双向循环链表 定义结点 一、双向链表...

  • 算法与数据结构:链表

    链表 链表还分为单向链表和双向链表, 但是这篇文章只说单向链表 , 下次再讲双向链表 . 链表和数组的区别 ? 链...

  • 链表

    链表 单链表反转链表中环的检测两个有序链表合并删除链表倒数第n个节点求链表的元素总个数 一.单向链表 链表共有特征...

  • 五、双向链表

    双向链表 此前介绍的链表,也叫做单向链表使用双向链表可以提升链表的综合性能 修改之前的单链表的源码: 双向链表 –...

  • 链表

    内容 链表数据结构 向链表添加元素 从链表移除元素 使用 LinkedList 表 双向链表 循环链表 链表数据结...

  • 数据与算法结构

    线性表 顺序表 链表(物理上离散,逻辑上连续) 链表的类别 单链表 循环链表 双链表 链表的操作 顺序表与链表的比...

  • 数据结构——链表

    本文所讲的链表是单链表,链表采用无头链表 科普下:一般链表可以分为有头节点的链表与无头节点的链表 有头节点的链表:...

  • 链表

    文章结构 链表的定义 链表的插入和删除操作 链表的特性 常见的链表结构 自定义链表 链表的经典操作 使用链表实现L...

  • Algorithm小白入门 -- 单链表

    单链表递归反转链表k个一组反转链表回文链表 1. 递归反转链表 单链表节点的结构如下: 1.1 递归反转整个单链表...

网友评论

      本文标题:链表

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