实现链表
实现链表
链表节点示例：
private:
template <typename E>
class Node {
public:
E val;
Node* next;
Node* prev;
Node(Node* prev, E element, Node* next) {
this->val = element;
this->next = next;
this->prev = prev;
}
};
class Node:
def __init__(self, prev, element, next):
self.prev = prev
self.val = element
self.next = next
链表实现
小技巧：虚拟头结点 设虚拟头节点、尾节点分别为dummyhead, dummytail,则链表如下所示：
1
dummyhead<->dummytail
若添加3个元素：
1
dummyhead<->1<->2<->3<->dummytail
引入虚拟头尾结点前，需要对插入元素的位置进行讨论，引入后则无需讨论，简化操作，但会占用一定空间 对于单链表，虚拟尾结点无太大作用
单链表实现：
C++实现：
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
167
#include <iostream>
class MyLinkedList {
private:
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(nullptr) {}
};
ListNode* head;
ListNode* tail;
int size;
public:
MyLinkedList() {
head = new ListNode(-1);
tail = head;
size = 0;
}
//查
int get(int index) {
if (!checkElementIndex(index)) {
return -1;
};
//注意这里的p不同
ListNode* p = head->next;
for (int i = 0; i < index; i++) {
p = p->next;
}
return p->val;
}
//增
void addAtHead(int val) {
ListNode* newNode = new ListNode(val);
newNode->next = head->next;
head->next = newNode;
if (size == 0) {
tail = newNode;
}
size++;
}
void addAtTail(int val) {
ListNode* newNode = new ListNode(val);
tail->next = newNode;
tail = newNode;
size++;
}
void addAtIndex(int index, int val) {
if (!checkPositionIndex(index)) {
return;
};
if (index == size) {
addAtTail(val);
return;
}
ListNode* newNode = new ListNode(val);
ListNode* p = head;
for (int i = 0; i < index; i++) {
p = p->next;
}
newNode->next = p->next;
p->next = newNode;
size++;
}
//删
void deleteLast() {
if (isEmpty()) {
throw std::out_of_range("No element to delete");
}
ListNode* p = head;
while (p->next != tail) {
p = p->next;
}
p->next = nullptr;
//必须先delete再赋值，否则原来指向的Node变为孤立的内存块，造成内存泄漏
delete tail;
tail = p;
size--;
}
void deleteFirst() {
if (isEmpty()) {
throw std::out_of_range("No element to delete");
}
ListNode* first = head->next;
head->next = first->next;
if (size == 1) {
tail = head;
}
size--;
delete first;
}
void deleteAtIndex(int index) {
if (!checkElementIndex(index)) {
return;
};
ListNode* p = head;
for (int i = 0; i < index; i++) {
p = p->next;
}
ListNode* oldNode = p->next;
p->next = oldNode->next;
if (index == size - 1) {
tail = p;
}
delete oldNode;
size--;
}
//改
void set(int index, int newval) {
checkElementIndex(index);
//注意这里的p不同
ListNode* p = head->next;
for (int i = 0; i < index; i++) {
p = p->next;
}
p->val = newval;
}
//工具
bool isElementIndex(int index) {
return index >= 0 && index < size;
}
bool isPositionIndex(int index) {
return index >= 0 && index <= size;
}
bool checkElementIndex(int index) {
if (!isElementIndex(index)) {
return 0;
} else {
return 1;
}
}
bool checkPositionIndex(int index) {
if (!isPositionIndex(index)) {
return 0;
} else {
return 1;
}
}
bool isEmpty() {
return size == 0;
}
~MyLinkedList() {
ListNode* current = head;
while (current != nullptr)
{
ListNode* next = current->next;
delete current;
current = next;
}
}
};
Python实现：
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
class MyLinkedList:
class ListNode:
def __init__(self, val):
self.val = val
self.next = None
def __init__(self):
self.head = self.ListNode(None)
self.tail = self.head
self.size = 0
def get(self, index):
if not self.checkElementIndex(index):
return -1
p = self.head.next
for i in range(index):
p = p.next
return p.val
def addAtHead(self, val):
newNode = self.ListNode(val)
newNode.next = self.head.next
self.head.next = newNode
if self.size == 0:
self.tail = newNode
self.size += 1
def addAtTail(self, val):
newNode = self.ListNode(val)
self.tail.next = newNode
self.tail = newNode
self.size += 1
def addAtIndex(self, index, val):
if not self.checkPositionIndex(index):
return -1
p = self.head
newNode = self.ListNode(val)
for i in range(index):
p = p.next
newNode.next = p.next
p.next = newNode
if newNode.next is None:
self.tail = newNode
self.size += 1
def deleteFirst(self):
if self.size == 0:
return
oldNode = self.head.next
self.head.next = oldNode.next
if self.size == 1:
self.tail = self.head
self.size -= 1
def deleteLast(self):
if self.size == 0:
return
p = self.head
while p.next != self.tail:
p = p.next
p.next = None
self.tail = p
self.size -= 1
def deleteAtIndex(self, index):
if not self.checkElementIndex(index):
return -1
p = self.head
for i in range(index):
p = p.next
oldNode = p.next
p.next = oldNode.next
if p.next is None:
self.tail = p
self.size -= 1
def isElementIndex(self, index):
return 0 <= index < self.size
def isPositionIndex(self, index):
return 0 <= index <= self.size
def checkElementIndex(self, index):
return self.isElementIndex(index)
def checkPositionIndex(self, index):
return self.isPositionIndex(index)
双链表实现：
c++实现：
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
#include <iostream>
class MyLinkedList {
private:
struct ListNode {
int val;
ListNode* next;
ListNode* prev;
ListNode(int x) : val(x), next(nullptr), prev(nullptr) {}
};
ListNode* head;
ListNode* tail;
int size;
public:
MyLinkedList() {
head = new ListNode(-1);
tail = new ListNode(-1);
head->next = tail;
tail->prev = head;
size = 0;
}
~MyLinkedList() {
ListNode* p = head;
while (p != nullptr) {
ListNode* temp = p->next;
delete p;
p = temp;
}
head = nullptr;
tail = nullptr;
}
//查
int get(int index) {
if (!checkElementIndex(index)) {
return -1;
}
ListNode* p = head->next;
for (int i = 0; i < index; i++) {
p = p->next;
}
return p->val;
}
//增
void addAtHead(int val) {
ListNode* newNode = new ListNode(val);
newNode->prev = head;
if (size == 0) {
newNode->next = tail;
} else {
newNode->next = head->next;
}
head->next->prev = newNode;
head->next = newNode;
size++;
}
void addAtTail(int val) {
ListNode* newNode = new ListNode(val);
newNode->next = tail;
if (size == 0) {
newNode->prev = head;
} else {
newNode->prev = tail->prev;
}
tail->prev->next = newNode;
tail->prev = newNode;
size++;
}
void addAtIndex(int index, int val) {
if (!checkPositionIndex(index)) {
return;
}
if (index == size) {
addAtTail(val);
return;
}
ListNode* p = head;
ListNode* newNode = new ListNode(val);
for (int i = 0; i < index; i++) {
p = p->next;
}
newNode->next = p->next;
newNode->prev = p;
p->next->prev = newNode;
p->next = newNode;
size++;
}
//删
void deleteLast() {
if (size == 0) {
return;
}
ListNode* oldNode = tail->prev;
ListNode* temp = tail->prev->prev;
tail->prev = temp;
temp->next = tail;
oldNode->prev = nullptr;
oldNode->next = nullptr;
delete oldNode;
size--;
}
void deleteFirst() {
if (size == 0) {
return;
}
ListNode* oldNode = head->next;
ListNode* temp = head->next->next;
head->next = temp;
temp->prev = head;
oldNode->next = nullptr;
oldNode->prev = nullptr;
delete oldNode;
size--;
}
void deleteAtIndex(int index) {
if (!checkElementIndex(index)) {
return;
}
ListNode* p = head;
for (int i = 0; i < index; i++) {
p = p->next;
}
ListNode* oldNode = p->next;
ListNode* temp = p->next->next;
p->next = temp;
temp->prev = p;
oldNode->next = nullptr;
oldNode->prev = nullptr;
delete oldNode;
size--;
}
//工具
bool isElementIndex(int index) {
return index >= 0 && index < size;
}
bool isPositionIndex(int index) {
return index >= 0 && index <= size;
}
bool checkElementIndex(int index) {
if (!isElementIndex(index)) return 0;
else return 1;
}
bool checkPositionIndex(int index) {
if (!isPositionIndex(index)) return 0;
else return 1;
}
};
Python实现：
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
class MyLinkedList:
class ListNode:
def __init__(self, val):
self.val = val
self.next = None
self.prev = None
def __init__(self):
self.head = self.ListNode(None)
self.tail = self.ListNode(None)
self.head.next = self.tail
self.tail.prev = self.head
self.size = 0
def get(self, index):
if not self.checkElementIndex(index):
return -1
p = self.head.next
for i in range(index):
p = p.next
return p.val
def addAtHead(self, val):
newNode = self.ListNode(val)
newNode.prev = self.head
if self.size == 0:
newNode.next = self.tail
else:
newNode.next = self.head.next
self.head.next.prev = newNode
self.head.next = newNode
self.size += 1
def addAtTail(self, val):
newNode = self.ListNode(val)
newNode.next = self.tail
if self.size == 0:
newNode.prev = self.head
else:
newNode.prev = self.tail.prev
self.tail.prev.next = newNode
self.tail.prev = newNode
self.size += 1
def addAtIndex(self, index, val):
if not self.checkPositionIndex(index):
return
p = self.head
newNode = self.ListNode(val)
for i in range(index):
p = p.next
newNode.next = p.next
newNode.prev = p
p.next.prev = newNode
p.next = newNode
self.size += 1
def deleteFirst(self):
if self.size == 0:
return
oldNode = self.head.next
temp = oldNode.next
self.head.next = temp
temp.prev = self.head
self.size -= 1
def deleteLast(self):
if self.size == 0:
return
oldNode = self.tail.prev
temp = oldNode.prev
temp.next = self.tail
self.tail.prev = temp
self.size -= 1
def deleteAtIndex(self, index):
if not self.checkElementIndex(index):
return
p = self.head
for i in range(index):
p = p.next
oldNode = p.next
temp = oldNode.next
p.next = temp
temp.prev = p
self.size -= 1
def set(self, index, val):
if not self.checkElementIndex(index):
return
p = self.head.next
for i in range(index):
p = p.next
p.val = val
def isElementIndex(self, index):
return 0 <= index < self.size
def isPositionIndex(self, index):
return 0 <= index <= self.size
def checkElementIndex(self, index):
return self.isElementIndex(index)
def checkPositionIndex(self, index):
return self.isPositionIndex(index)
This post is licensed under CC BY 4.0 by the author.