链表

Posted on | In

一、链表是什么？与数组有什么区别？生活中有什么例子？

1）链式存储的线性表，相连属性通过指针链接，将一系列不连续的内存联系起来，将那种碎片内存进行合理的利用，解决空间的问题。

2）

数组：使用一块连续的内存空间存储，每个元素有指定的索引值，增删的时候，要移动目标位置之后的所有元素。

链表：查询元素慢，没有索引值，必须遍历整个链表，增删的时候，只要改变相连元素之间的指针就可以了

3）有点像上体育课的时候排队，排在每个人左边和右边的人有个对应的关系，并且询问每个人就能知道左边和右边是谁。

二、请实现一个链表，并实现以下方法：

WX20190721-210322@2x

  • append(element)：向链表尾部添加一个新的元素。
  • insert(position, element)：向链表指定位置插入一个新的元素。
  • remove(element)：从链表中移除并返回已删除的元素（若有多个相同元素则取第一次出现的情况）。
  • getNode(position)：获取指定索引位置的节点。
  • indexOf(element)：返回元素在链表中的索引（若有多个相同元素则取第一次出现的情况），如果列表中没有该元素则返回 -1。
  • removeAt(position)：从链表特定的位置移除一项。
  • getHead()：获取链表头部。
  • getTail()：获取链表尾部。
  • isEmpty()：如果链表中不包含任何元素，返回 true，否则返回 false。
  • size()：返回链表中元素个数，与数组的 length 属性类似。
  • print()：打印链表中的所有元素，如 “0@1–>1@2–>2@3–>3@4–>4@5”（”index@element”）。
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
function Node(element) {
    this.element = element;
    this.next = null
}
class LinkedList {
    constructor() {
        this.head = null;
        this.tail = null;
        this.length = 0;
    }
    append(element) {
        let node = new Node(element);
        if (this.head) {
            this.tail.next = node;
        } else {
            this.head = node;
        }
        this.tail = node;
        this.length++;
    }
    insert(position, element) {
        if (position >= 0 && position <= this.length) {
            let node = new Node(element);
            if (position === 0) {//如果是0，在第一项插入
                node.next = this.head;
                thi.head = node;
            } else {
                let pre, index = 0, head = this.head;
                while (position > index) {
                    index++;
                    pre = head;
                    head = head.next;
                }
                position === this.length && (this.tail = node);
                pre.next = node;
                node.next = head;
            }
            this.length++;
        }
    }
    remove(element) {
        if (this.length) {
            if (element === this.head.element) {//如果等于首位
                let removeElement;
                removeElement = this.head;
                this.head = this.head.next;
                if (this.length === 1) this.tail = null;
                this.length--;
                return removeElement;
            } else {
                let pre, head = this.head;
                while (head && head.element !== element) {
                    pre = head;
                    head = head.next;
                }
                if (head && head.element === element) {
                    pre.next = head.next;
                    !head.next && (this.tail = pre);
                    this.length--;
                    return head;
                } else {
                    return undefined;
                }
            }
        }
    }
    getNode(position) {
        if (position >= 0 && position <= this.length) {
            let index = 0, head = this.head;
            while (index !== position) {
                index++;
                head = head.next;
            }
            return head;
        }
    }
    indexOf(element) {
        let index = 0, head = this.head;
        if (element === head.element) {
            return 0;
        } else {
            while (head && head.element !== element) {
                head = head.next;
                index++;
            }
            if (head) {
                return index;
            } else {
                return;
            }
        }
    }
    removeAt(position) {
        if (position >= 0 && position < this.length) {
            if (position === 0) {//移除第一位
                this.head = this.head.next;
                if (this.length === 1) this.tail = null;
            } else {
                let pre, index = 0, head = this.head;
                while (index != position) {
                    index++;
                    pre = head
                    head = head.next;
                }
                pre.next = head.next;
                !head.next && (this.tail = pre);
            }
            this.length--;
        }
    }
    getHead() {
        return this.head;
    }
    getTail() {
        return this.tail;
    }
    isEmpty() {
        return !this.length;
    }
    size() {
        return this.length;
    }
    print() {
        let head = this.head, arr = [], index = 0;
        while (head) {
            arr.push(`${index}@${head.element}`);
            index++;
            head = head.next;
        }
        return arr.join('-->');
    }
}

三、基于链表分别实现 Stack 和 Queue

栈

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
class Stack {
    constructor() {
        this.linkedList = new LinkedList();
    }
    push(element) {
        this.linkedList.append(element);
    }

    pop() {
        const tail = this.linkedList.getTail().element;
        this.linkedList.removeAt(this.linkedList.length - 1);
        return tail;
    }

    peek() {
        return this.linkedList.getTail().element;
    }

    isEmpty() {
        return this.linkedList.isEmpty();
    }

    size() {
        return this.linkedList.size();
    }

    clear() {
        this.linkedList = new LinkedList();
    }
}

队列

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
class Queue {
    constructor() {
        this.linkedList = new LinkedList();
    }
    enqueue(element) {
        this.linkedList.append(element);
    }
    dequeue() {
        const head = this.linkedList.getHead();
        this.linkedList.removeAt(0);
        return head && head.element;
    }
    front() {
        return this.linkedList.getHead() && this.linkedList.getHead().element;
    }
    tail() {
        return this.linkedList.getTail() && this.linkedList.getTail().element;
    }
    isEmpty() {
        return this.linkedList.isEmpty();
    }
    size() {
        return this.linkedList.length;
    }
}

四、链表反转

请实现一个 reverseLinkedList() 方法，用于实现链表反转。

WX20190721-210356@2x

1
2
3
4
5
6
7
8
9
10
function reverseLinkedList(head) {
    let current = head, pre = null;
    while (head) {
        current = head;
        head = head.next;
        current.next = pre;
        pre = current;
    }
    return current
}

五、请实现一个双向链表 DoublyLinkedList

  • insert(position, element)：向链表指定位置插入一个新的元素。
  • removeAt(position)：从链表特定的位置移除一项。

WX20190721-233449@2x

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
function Node(element) {
    this.pre = null;
    this.element = element;
    this.next = null;
}

class DoublyLinkedList {
    constructor() {
        this.head = null;
        this.tail = null;
        this.length = 0;
    }
    insert(position, element) {
        if (position >= 0 && position <= this.length) {
            let node = new Node(element);
            if (this.length === 0) {//链表为空
                this.head = node;
                this.tail = node;
            } else {
                let pre, index = 0, current = this.head;
                while (position !== index) {
                    pre = current;
                    current = current.next;
                    index++;
                }
                pre.next = node;

                node.pre = pre;
                node.next = current;
                if (current) {
                    current.pre = node;
                } else {
                    this.tail = node;
                }
            }
            this.length++;
            return true;
        } else {
            return false;
        }
    }
    removeAt(position) {
        if (position >= 0 && position < this.length) {
            if (position === 0) {
                if (this.length === 0) {
                    this.head = null;
                    this.tail = null;
                } else {
                    this.head = this.head.next;
                    this.head.pre = null;
                }
                this.length--;
            } else {
                let pre, current = this.head, index = 0;
                while (position !== index) {
                    pre = current;
                    current = current.next;
                    index++;
                }
                if(current && current.next){
                    pre.next = current.next;
                    current.next.pre = pre;
                }else if(current && !current.next){ 
                    pre.next = null;
                    this.tail = pre;
                }
                this.length--;
            }
            return true;
        } else {
          return null;
        }
    }
}