关于javascript:JS数据结构-单向链表

单向链表

• 链表存储有序失去元素汇合，但不同于数组，链表中的元素在内存中并不是间断搁置的。
• 每个元素是由一个存储元素自身的节点和一个指向下一个元素的援用（也称指针的或链接）组成。

留神：

1. 绝对于传统的数组，链表的一个益处在于，增加或移除元素的时候不须要挪动其余元素。
2. 然而，链表须要应用指针，因而实现链表时须要额定留神。
3. 在数组中，咱们能够间接拜访任何地位的任何元素，而要想拜访链表两头的一个元素，则须要从终点（表头）开始迭代链表直到找到所需的元素

举个简略的例子：

• 寻宝游戏：你有一条线索，这条线索就是指向寻找下一条线索的地点的指针，顺着这条链接去下一个地点，失去另一条指向在下一处的线索，失去链表两头的线索的惟一方法，就是从终点（第一条线索）顺着链表寻找
• 火车：一列火车是由一系列车厢组成，每节车厢都相互连贯。你很容易拆散一节车厢，扭转它的地位，增加或移除它。每节车厢都是链表的元素，车厢间的连贯就是指针。

链表类办法

• push(element)/append(element):向链表尾部增加一个新元素
• insert(position,element):向链表非凡地位插入一个新的元素
• get(position):获取对应地位的元素
• indexOf(element):返回元素在列表中的索引。如果列表中没有该元素则返回
• update(positon,element):批改某个地位的元素
• removeAt(position):从列表的特定地位移除一项
• remove(element):从列表中移除一项
• isEmpty():如果链表中不包含任何元素，会犯true，如果链表长度大于则返回false
• size():返回链表蕴含的元素个数。与数组length相似

实现链表：

class LinkedList {
    constructor() {
            this.head = null
            this.length = 0
        }

• append(element):向链表尾部追加数据

    append(element) {
            const newNode = new Node(element);
            // 追加到最初
            if (!this.head) {
                this.head = newNode
            } else {
                let current = this.head;
                while (current.next) {
                    current = current.next
                }
                current.next = newNode
            }
            this.length++
        }

• insert(position,element):向链表非凡地位插入一个新的项

    insert(position, element) {
            //判断越界问题
            if (position < 0 || position > this.length) return false
                // 创立新的节点
            const newNode = new Node(element)
                // 插入元素
            if (position === 0) {
                newNode.next = this.head
                this.head = newNode
            } else {
                let index = 0
                let current = this.head
                let previous = null
                while (index++ < position) {
                    previous = current
                    current = current.next
                }
                previous.next = newNode
                newNode.next = current
            }
            this.length++
                return true
        }

• get(position):获取对应地位的元素

    get(position) {
        if (position < 0 || position > this.length - 1) return null
            // 查找该地位的元素
        let index = 0
        let current = this.head
        while (index++ < position) {
            current = current.next
        }
        return current.element
    }
  

• indexOf(element):返回元素在列表中的索引。如果列表中没有该元素则返回-1

    indexOf(element) {
            // 獲取第一個元素
            let current = this.head
            let index = 0
                // 開始查找
            while (current) {
                if (current.element === element) {
                    return index
                }
                index++
                current = current.next
            }
            return -1
        }

• update(positon,element):批改某个地位的元素

    update(positon, element) {
            // 刪除position地位的元素，间接调用咱们封装好的就好
            const result = this.removeAt(positon)
            // 插入position，间接调用咱们封装好的就好
            this.insert(positon, element)
            return result
        }

• removeAt(position):从列表的特定地位移除一项

    removeAt(position) {
        if (position < 0 || position > this.length - 1) return null
            // 刪除元素
        let current = this.head
        let previous = null
        let index = 0
            // 
        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):从列表中移除一项

    remove(element) {
            // 獲取地位
            const index = this.indexOf(element)
            if (index === -1) return
                // 刪除該地位的元素
            this.removeAt(index)
        }

• isEmpty():如果链表中不包含任何元素，会犯true，如果链表长度大于则返回false

    isEmpty() {
            return this.length === 0
        }

• size():返回链表蕴含的元素个数。与数组length相似

    size() {
        return this.length
    }
  }
  

测试方法是否胜利

• 测试append

const linkedList = new LinkedList()
linkedList.append('aaa')
linkedList.append('bbb')
linkedList.append('ccc')
linkedList.append('ddd')

console.log(linkedList)//输入length 为4的链表，每个node有各自对应的值

• 测试insert

linkedList.insert(1, 'abc')
linkedList.insert(3, 'cba')

console.log(linkedList)//输入length 为6的链表，每个node有各自对应的值

• 測試position

console.log(linkedList.get(1))//输入abc
console.log(linkedList.get(3))//输入cba

• 測試indexof

console.log(linkedList.indexOf('abc'))//输入1
console.log(linkedList.indexOf('cba'))//输入3
console.log(linkedList.indexOf('asdsd'))//输入-1(定义查不到返回-1)

• 測試removeAt

console.log(linkedList.removeAt(3))//输入cba
console.log(linkedList.removeAt(1))//输入abc
console.log(linkedList)//此时链表length 为4 因为调用删除

• 測試update

console.log(linkedList.update(1, 'npc'))//输入bbb（留神：在这里不设置返回值，会输入undefined，但无伤大雅，曾经设置）
console.log(linkedList)//此时将bbb更新为npc，链表length为4

• 測試remove

linkedList.remove('aaa')
console.log(linkedList)//此时链表length为3

• 測試isEmpty

console.log(linkedList.isEmpty())//输入false

• 測試size

console.log(linkedList.size())//输入3