链表数据结构_链表的元素在内存中不可以连续存放

链表

一种动态的数据结构，会按需扩容。

链表存储有序的元素集合，链表的元素在内存中不是连续存放的，每一个元素是由元素本身节点和指向下一个元素的引用（指针或者是链接）构成。

在访问链表的时候，需要从起点开始迭代链表，直到找到指定元素位置

双向链表

每个元素都有指向下一个和上一个元素的链，

循环链表

结构包含了链表和双向链表

循环链表和链表之间的区别在于，最后一个元素指向下一个元素的指针【tail.next】不是undefined，而是指向第一个元素【head】

/*
 * @FileName: 链表
 * @Author: duxinyue
 * @Date: 2021-04-29 14:30:00
 * @LastEditors: duxinyue
 * @LastEditTime: 2021-05-04 00:53:27
 * @FilePath: \JavaScript\dataStructure\linkedList.js
 * @Description: 链表的结构
 */
import {
    defaultEquals
} from "../utils/util.js";
import {
    Node
} from "../models/linked-list-models.js"

export  class LinkedList {
    constructor(equalsFn = defaultEquals) {
        this.count = 0; //存储链表元素的数量
        this.head = undefined; // 第一个元素的引用
        this.equalsFn = equalsFn
    }
    /**
     *  向链表尾部添加元素
     * @param {*} element 
     * 如果链表是空，则添加的是第一个元素，否则添加的是最后一个元素
     */
    push(element) {
        const node = new Node(element);
        let current;
        if (this.head == undefined) {
            this.head = node;
        } else {
            current = this.head;
            while (current.next != null) {
                // 最后一项
                current = current.next
            }
            // 将next赋为新元素，建立链接
            current.next = node;
        }
        this.count++; //递增链表的长度
    }
    /**
     * 删除链表中的元素【根据位置删除元素】
     * @param {*} index 
     */
    removeAt(index) {
        // 检查链表的边界数值
        if (index >= 0 && index < this.count) {
            let current = this.head; // 当前元素的引用
            if (index === 0) {
                this.head = current.next;
            } else {
                // 因为查找链表中的某一个元素，只能从头开始查询
                const previous = this.getElementAt(index - 1); // 当前元素的前一个元素的引用
                current = current.next;
                previous.next = current.next;
            }
            this.count--;
            return current.element
        }
        return undefined // 超出链表边界的话返回undefined
    }
    /**
     * 迭代链表，一直到目标位置
     * @param {*} index 
     */
    getElementAt(index) {
        if (index >= 0 && index <= this.count) {
            let node = this.head;
            for (let key = 0; key < index && node != null; key++) {
                node = node.next;
            }
            return node;
        }
        return undefined;
    }
    /**
     * 链表任意位置插入元素
     * @param {*} element 
     * @param {*} index 
     */
    insert(element, index) {
        // 判断链表的边界
        if (index >= 0 && index <= this.count) {
            const node = new Node(element);
            if (index === 0) {
                const current = this.head;
                node.next = current;
                this.head = node;
            } else {
                const previous = this.getElementAt(index - 1); // 当前元素的上一个元素引用
                const current = previous.next;
                node.next = current;
                previous.next = node;
            }
            this.count++;
            return true
        }
        return false;
    }
    /**
     * 返回一个元素的位置
     * @param {*} element 
     */
    indexOf(element) {
        let current = this.head;
        for (let index = 0; index < this.count && current != null; index++) {
            if (this.equalsFn(element, current.element)) {
                return index;
            }
            current = current.next
        }
        return -1;
    }
    /**
     * 根据元素删除链表元素
     * @param {*} element 
     */
    remove(element) {
        const index = this.indexOf(element);
        return this.removeAt(index);
    }

    size() {
        return this.count;
    }

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

    getHead() {
        return this.head;
    }

    toString() {
        if (this.head == null) {
            return ""
        }
        let objString = `${this.head.element}`;
        let current = this.head.next;
        for (let index = 1; index < this.size() && current != null; index++) {
            objString = `${objString},${current.element}`;
            current = current.next;
        }
        console.log(objString)
        return objString;
    }
}


const list = new LinkedList();
list.push(12)
list.push(23)
list.push("duxin")
list.insert(1111, 0)
console.log(list.count)
console.log(list.head)
console.log(list.indexOf("0"))
list.removeAt(1);
console.log("删除后的链表==", list.head)

console.log(list.getHead())
console.log(list.toString())
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166