数据结构-链表

单链表

是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的，每个结点的构成：元素(数据元素的映象) + 指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。

单链表是链表的其中一种基本结构。在结点中数据域用来存储数据元素，指针域用于指向下一个具有相同结构的结点。
因为只有一个指针结点，称为单链表。

头结点、头指针和首元结点

• 头结点：有时，在链表的第一个结点之前会额外增设一个结点，结点的数据域一般不存放数据（有些情况下也可以存放链表的长度等信息），此结点被称为头结点。

  若头结点的指针域为空（NULL），表明链表是空表。头结点对于链表来说，不是必须的，在处理某些问题时，给链表添加头结点会使问题变得简单。

  • 首元结点：链表中第一个元素所在的结点，它是头结点后边的第一个结点。

  • 头指针：永远指向链表中第一个结点的位置（如果链表有头结点，头指针指向头结点；否则，头指针指向首元结点）。

  头结点和头指针的区别：头指针是一个指针，头指针指向链表的头结点或者首元结点；头结点是一个实际存在的结点，它包含有数据域和指针域。两者在程序中的直接体现就是：头指针只声明而没有分配存储空间，头结点进行了声明并分配了一个结点的实际物理内存。

  // 封装链表的构造函数
    function LinkedList() {
        // 封装一个Node类, 用于保存每个节点信息
        function Node(element) {
            this.element = element
            this.next = null
        }

        // 链表中的属性
        this.length = 0
        this.head = null

        // 链表尾部追加元素方法
        LinkedList.prototype.append = function (element) {
            // 1.根据新元素创建节点
            var newNode = new Node(element)

            // 2.判断原来链表是否为空
            if (this.head === null) { // 链表尾空
                this.head = newNode
            } else { // 链表不为空
                // 2.1.定义变量, 保存当前找到的节点
                var current = this.head
                while (current.next) {
                    current = current.next
                }

                // 2.2.找到最后一项, 将其next赋值为node
                current.next = newNode
            }

            // 3.链表长度增加1
            this.length++
        }

        // 链表的toString方法
        LinkedList.prototype.toString = function () {
            // 1.定义两个变量
            var current = this.head
            var listString = ""

            // 2.循环获取链表中所有的元素
            while (current) {
                listString += "," + current.element
                current = current.next
            }

            // 3.返回最终结果
            return listString.slice(1)
        }

        // 根据下标插入元素
        LinkedList.prototype.insert = function (position, element) {
            // 1.检测越界问题: 越界插入失败 （当postion 为最后this.length时，插入其实就类似于append方法）
            if (position < 0 || position > this.length) return false

            // 2.定义变量, 保存信息
            var newNode = new Node(element)
            var current = this.head // 当前元素
            var previous = null // 保存上一个元素
            index = 0

            // 3.判断是否列表是否在第一个位置插入
            if (position == 0) {
                newNode.next = current
                this.head = newNode
            } else {
                while (index++ < position) {
                    previous = current
                    current = current.next
                }

                newNode.next = current
                previous.next = newNode
            }

            // 4.length+1
            this.length++

            return true
        }

        // 根据位置移除节点
        LinkedList.prototype.removeAt = function (position) {
            // 1.检测越界问题: 越界移除失败, 返回null （可以操作的postion 是 0 到 length-1）
            if (position < 0 || position >= this.length) return null

            // 2.定义变量, 保存信息
            var current = this.head
            var previous = null
            var index = 0

            // 3.判断是否是移除第一项
            if (position === 0) {
                this.head = current.next
            } else {
                while (index++ < position) {
                    previous = current
                    current = current.next
                }

                previous.next = current.next
            }

            // 4.length-1
            this.length--

            // 5.返回移除的数据
            return current.element
        }

        // 根据元素获取链表中的位置
        LinkedList.prototype.indexOf = function (element) {
            // 1.定义变量, 保存信息
            var current = this.head
            index = 0

            // 2.找到元素所在的位置
            while (current) {
                if (current.element === element) {
                    return index
                }
                index++
                current = current.next
            }

            // 3.来到这个位置, 说明没有找到, 则返回-1
            return -1
        }

        // 根据元素删除信息
        LinkedList.prototype.remove = function (element) {
            var index = this.indexOf(element)
            return this.removeAt(index)
        }

        // 判断链表是否为空
        LinkedList.prototype.isEmpty = function () {
            return this.length == 0
        }

        // 获取链表的长度
        LinkedList.prototype.size = function () {
            return this.length
        }

        // 获取第一个节点
        LinkedList.prototype.getFirst = function () {
            return this.head.element
        }
    }

双向链表

双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。

头指针的指针域储存着储存头节点的地址
尾指针的指针域存储着储存尾节点的地址

单链表的缺陷

单链表只能从头结点开始访问链表中的数据元素，如果需要逆序访问单链表中的数据元素将极其低效。

   // 创建双向链表的构造函数
    function DoublyLinkedList() {
        // 创建节点构造函数
        function Node(element) {
            this.element = element
            this.next = null // 指向前一个节点
            this.prev = null // 指向后一个节点
        }

        // 定义属性
        this.length = 0
        this.head = null // 头指针 指向第一个节点
        this.tail = null // 尾指针 指向最后一个节点

        // 定义相关操作方法
        // 在尾部追加数据
        DoublyLinkedList.prototype.append = function (element) {
            // 1.根据元素创建节点
            var newNode = new Node(element)

            // 2.判断列表是否为空列表
            if (this.head == null) {
                this.head = newNode
                this.tail = newNode
            } else {
                this.tail.next = newNode
                newNode.prev = this.tail
                this.tail = newNode
            }

            // 3.length+1
            this.length++
        }

        // 在任意位置插入数据
        DoublyLinkedList.prototype.insert = function (position, element) {
            // 1.判断越界的问题
            if (position < 0 || position > this.length) return false

            // 2.创建新的节点
            var newNode = new Node(element)

            // 3.判断插入的位置
            if (position === 0) { // 在第一个位置插入数据
                // 判断链表是否为空
                if (this.head == null) {
                    this.head = newNode
                    this.tail = newNode
                } else {
                    this.head.prev = newNode
                    newNode.next = this.head
                    this.head = newNode
                }
            } else if (position === this.length) { // 插入到最后的情况
                // 思考: 这种情况是否需要判断链表为空的情况呢? 答案是不需要, 为什么?
                this.tail.next = newNode
                newNode.prev = this.tail
                this.tail = newNode
            } else { // 在中间位置插入数据
                // 定义属性
                var index = 0
                var current = this.head
                var previous = null

                // 查找正确的位置
                while (index++ < position) {
                    previous = current
                    current = current.next
                }

                // 交换节点的指向顺序
                newNode.next = current
                newNode.prev = previous
                current.prev = newNode
                previous.next = newNode
            }

            // 4.length+1
            this.length++

            return true
        }

        // 根据位置删除对应的元素
        DoublyLinkedList.prototype.removeAt = function (position) {
            // 1.判断越界的问题
            if (position < 0 || position >= this.length) return null

            // 2.判断移除的位置
            var current = this.head
            if (position === 0) {
                if (this.length == 1) {
                    this.head = null
                    this.tail = null
                } else {
                    this.head = this.head.next
                    this.head.prev = null
                }
            } else if (position === this.length -1) {
                current = this.tail
                this.tail = this.tail.prev
                this.tail.next = null
            } else {
                var index = 0
                var previous = null

                while (index++ < position) {
                    previous = current
                    current = current.next
                }

                previous.next = current.next
                current.next.prev = previous
            }

            // 3.length-1
            this.length--

            return current.element
        }

        // 根据元素获取在链表中的位置
        DoublyLinkedList.prototype.indexOf = function (element) {
            // 1.定义变量保存信息
            var current = this.head
            var index = 0

            // 2.查找正确的信息
            while (current) {
                if (current.element === element) {
                    return index
                }
                index++
                current = current.next
            }

            // 3.来到这个位置, 说明没有找到, 则返回-1
            return -1
        }

        // 根据元素删除
        DoublyLinkedList.prototype.remove = function (element) {
            var index = this.indexOf(element)
            return this.removeAt(index)
        }

        // 判断是否为空
        DoublyLinkedList.prototype.isEmpty = function () {
            return this.length === 0
        }

        // 获取链表长度
        DoublyLinkedList.prototype.size = function () {
            return this.length
        }

        // 获取第一个元素
        DoublyLinkedList.prototype.getHead = function () {
            return this.head.element
        }

        // 获取最后一个元素
        DoublyLinkedList.prototype.getTail = function () {
            return this.tail.element
        }

        // 遍历方法的实现
        // 正向遍历的方法
        DoublyLinkedList.prototype.forwardString = function () {
            var current = this.head
            var forwardStr = ""

            while (current) {
                forwardStr += "," + current.element
                current = current.next
            }

            return forwardStr.slice(1)
        }

        // 反向遍历的方法
        DoublyLinkedList.prototype.reverseString = function () {
            var current = this.tail
            var reverseStr = ""

            while (current) {
                reverseStr += "," + current.element
                current = current.prev
            }

            return reverseStr.slice(1)
        }

        // 实现toString方法
        DoublyLinkedList.prototype.toString = function () {
            return this.forwardString()
        }
    }