Singly Linked Lists

初识

单链表的原理比较简单:单链表由一个个的节点组成,每个节点包含其要存储的数据和一个指针,其中指针指向下一个节点,由此串成一个单向的链表。容易算出,在非首部的任意位置n处,单链表的增删改查的复杂度都为O(n).在单链表的开始,即首部的增删改查均为O(1).与Array的复杂度对比具体可参考wiki这张表:

初步的实现:

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

class IntNode{
public:

int info;
IntNode* next;

IntNode(){
next = 0;
}

IntNode(int i, IntNode* in = 0){
info = i;
next = in;
};

};

// 打印链表
void printLinkedLists(IntNode* p ){
while(p != 0){
printf("%d\n", p->info);
p = p->next;
}
}


int main(){

IntNode* p = new IntNode(10);
p->next = new IntNode(8);
p->next->next = new IntNode(50);
printLinkedLists(p);

return 0;
}


输出:

10
8
50

一般实现
intSLLst.h
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

//
// Created by shensir on 17-4-24.
//

#ifndef CPPPROJECTS_INTSSLST_H_H
#define CPPPROJECTS_INTSSLST_H_H

class IntNode{
public:
int info;
IntNode* next;

IntNode(int el, IntNode* ptr = 0){
info = el; next = ptr;
}
};


class IntSLList{

private:
IntNode *head, *tail;

public:

IntSLList(){
head = tail = 0;
}
~IntSLList();

int isEmpty(){
return head==0;
}

void addToHead(int);
void addToTail(int);
int deleteFromHead(); // delete the head and return its info;
int deleteFromTail(); // delete the tail and return its info;
void deleteNodeFromEl(int);
void deleteNodeFromPos(int);
void addToLList(int el, int pos);
bool isInList(int) const;
void printLinkedLists();


};



#endif //CPPPROJECTS_INTSSLST_H_H


intSLLst.cpp
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

//
// Created by shensir on 17-4-24.
//
#include <iostream>
#include <assert.h>
#include "intSSLst.h"

IntSLList::~IntSLList(){
for(IntNode *p; !isEmpty();){
p = head->next;
delete head;
head = p;
}
}

void IntSLList::addToHead(int el) {
head = new IntNode(el, head);
if(tail == 0)
tail = head;
}



void IntSLList::addToTail(int el) {
if(tail!=0){ // if list not empty
tail->next = new IntNode(el);
tail = tail->next;
}

else head = tail = new IntNode(el);
}


int IntSLList::deleteFromHead() {
if(isEmpty())
throw("Empty"); // 若为空表,从头部删除的话就抛出错误

int el = head->info;
IntNode *tmp = head;
if(head == tail) // if only one node in the list
head = tail = 0;
else head = head->next;
delete tmp;
return el;
}


int IntSLList::deleteFromTail() {
int el = tail->info;
if(head == tail){
delete head;
head = tail = 0;
}
else{ // if more than one node in the list
IntNode * tmp; // find the predecessor of tail
for(tmp=head; tmp->next!=tail;tmp=tmp->next);
delete tail;
tail = tmp;
tail->next = 0;
}
return el;
}


void IntSLList::deleteNodeFromEl(int el) {
if(head != 0){ // if non-empty list
if(head == tail && el == head->info){ // if only one
delete head; // node in the list
head = tail = 0;
}
else if(el == head->info){ // if more than one node in the list
IntNode* tmp = head; // 原文是head->next, 应该是错了
head = head->next;
delete tmp; // and old head is deleted
}
else{// if mpre than onde node in the lsit
IntNode *pred, *tmp;
for(pred = head, tmp = head->next; tmp!=0 && !(tmp->info == el);
pred = pred->next, tmp = tmp->next); // and a non-head node is deleted

if(tmp != 0){
pred->next = tmp->next;
if(tmp == tail)
tail = pred;;
delete tmp;
}

}

}

}


void IntSLList::deleteNodeFromPos(int pos) {
if(pos == 1)
deleteFromHead();
else if(pos == -1)
deleteFromTail();

else{
IntNode *tmp=head->next;
IntNode *pred = head;
for(int i=0; i<pos-2; i++, tmp = tmp->next, pred = pred->next);

pred->next = tmp->next;
delete tmp;
}
}




void IntSLList::addToLList(int el, int pos) {
if(pos == 1)
addToHead(el);
else if( pos == -1 )
addToTail(el);

else{
IntNode *tmp=head->next;
IntNode *pred = head;
for(int i=0; i<pos-2; i++, tmp = tmp->next, pred = pred->next);

IntNode* posNode = new IntNode(el);
posNode->next = tmp;
pred->next = posNode;
}

}



bool IntSLList::isInList(int el) const {
IntNode *tmp;
for(tmp = head; tmp !=0 && (!tmp->info == el); tmp = tmp->next);
return tmp != 0;
}


// print the gly linked lists
void IntSLList::printLinkedLists(){
IntNode* p = head;
while(p != 0){
printf("%d\n", p->info);
p = p->next;
}
}




main.cpp
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

#include <iostream>
#include <stdlib.h>
#include "intSSLst.h"

// Linked lists


int main(){
IntSLList list;
list.addToHead(50);
list.addToHead(8);
list.addToHead(10);
list.addToHead(13);


list.printLinkedLists();

try{
list.deleteFromHead();
}catch (char const * s){
std::cerr<<"Error: "<<s<<std::endl;
}

printf("After the deleting form head...\n");
list.printLinkedLists();

printf("After the deleting from pos: 2th...\n");
list.deleteNodeFromPos(2);
list.printLinkedLists();

printf("After the adding from pos: 2th...\n");
list.addToLList(77, 2);
list.printLinkedLists();


return 0;
}


输出:

13
10
8
50
After the deleting form head…
10
8
50
After the deleting from pos: 2th…
10
50
After the adding from pos: 2th…
10
77
50

new, delete and pointers

在理解上面的deleteFromHead函数时有些懵,模仿着做了个测试,可以帮助理解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

int main(){

int num1 = 1;
int num2 = 2;

int* Ptr1 = new int(num1);
int* Ptr2 = Ptr1; // Ptr2与Ptr1是指向同一个地址的指针
int* Ptr3 = &num2;

printf("%d\n", *Ptr1);
printf("%d\n", *Ptr2);
Ptr1 = Ptr3; // 这里Ptr2已经为新的指针,和Ptr3指向同一地址

delete Ptr2; // 释放Ptr2指向的内存,因为此时Ptr1已经和Ptr3指向了同一地址,所以不会受影响.

printf("%d\n", *Ptr1);
printf("%d\n", *Ptr2);
}


输出:

1
1
2
0

基于ADT的实现
ListADT.h
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

//
// Created by shensir on 17-8-13.
//

#ifndef MDATASTRUCTURE_LISTADT_H
#define MDATASTRUCTURE_LISTADT_H



// List ADT

template <typename E> class List{ // List ADT
private:
void operator = (const List&){} // Protect assignment
List(const List&){} // Protect copy constructor
public:
List(){} // Default constructor
virtual ~List(){} // Bae destructor

// Clear contents from the list, to make it empty
virtual void clear() = 0;

// Insert an element at the current location
// item: The element to be inserted
virtual void insert(const E& item) = 0;

// Append an element at the end of the list
// item: The element to be appended
virtual void append(const E& item) = 0;

// Remove and return the current element
// Return: the element that was removed
virtual E remove() = 0;

// Set the current position to the start of the list
virtual void moveToStart() = 0;

// Set the current position to the end of the list
virtual void moveToEnd() = 0;

// Move the current position one step left.
// No change if already at beginning
virtual void prev() = 0;

// Move the current position one step right.
// No change if already at end
virtual void next() = 0;

// Return: the number of elements in the list
virtual int length() const = 0;

// Return: the position of the current element
virtual int currPos() const = 0;

// Set current position
// pos: The position to make current
virtual void moveToPos(int pos) = 0;

// Return: The current element
virtual const E& getValue() const = 0;

// Print List
virtual void printList() const = 0;
};



#endif //MDATASTRUCTURE_LISTADT_H


ListADT.cpp

这里额外附带了基于数组的顺序表的实现。此外是基于节点类的实现,与上面基于struct的实现略有差别。

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
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222

#include <iostream>
#include <assert.h>

#include "ListADT.h"

const int defaultSize = 10;
// Array based list implementation
template <typename E>
class Alist: public List<E>{
private:
int maxSize; // Maximum size of list
int listSize; // Number of list items now
int curr; // Position of current element
E* listArray; // Array holding list elements
public:
Alist(int size=defaultSize){// Constructor
maxSize = size;
listSize = curr = 0;
listArray = new E[maxSize];
}

~Alist(){delete [] listArray;} // Destructor

void clear(){ // Reinitialize the list
delete [] listArray; // Remove the array
listSize = curr = 0; // Reset the size
listArray = new E[maxSize]; // Recreate array
}

// insert "it" at current position
void insert(const E& it){
assert(listSize < maxSize && "List capacity exceeded");
for(int i=listSize; i > curr; i--)
listArray[i] = listArray[i-1]; // shift to make room
listArray[curr] = it;
listSize++; // Increment list size
}

void append(const E& it){ // Append "it"
assert(listSize < maxSize && "List capacity exceeded");
listArray[listSize++] = it;
}

// Remove and return the current element
E remove(){
assert((curr > 0) && (curr < listSize) && "No element");
E it = listArray[curr]; // Copy the element
for(int i=curr; i<listSize-1; i++)
listArray[i] = listArray[i+1]; // shift them down
listSize--;
return it;
}

void moveToStart(){curr = 0;} // Reset position
void moveToEnd(){curr = listSize;} // Set at end
void prev(){if(curr != 0) curr--;} // Back up
void next(){if(curr < listSize) curr++;} // Next

// Return list size
int length() const { return listSize;}

// Return current position
int currPos() const { return curr;}

// Set current list position to "pos"
void moveToPos(int pos){
assert((pos>0) && (pos<listSize) && "Pos out of range");
curr = pos;
}

const E& getValue() const {// Return current element
assert((curr>=0) && (curr<listSize) && "No current element");
return listArray[curr];
}

// Print the list
void printList() const{
for(int i=0; i < listSize; i++){
std::cout << listArray[i] << " ";
}
std::cout << "\n";
}
};



// Singly linked list node
template <typename E> class Link{
public:
E element; // Value for the node
Link* next; // Pointer to next node in list

// Constructor
Link(const E& elemval, Link* nextval = NULL){
element = elemval;
next = nextval;
}
Link(Link* nextval=NULL){next=nextval;}
};



// Linked list implementation
template <typename E> class LList: public List<E>{
private:
Link<E>* head; // Pointer to list header
Link<E>* tail; // Pointer to last element
Link<E>* curr; // Pointer to current element
int cnt; // Size of list

void init(){ // Initialization helper method
curr = tail = head = new Link<E>;
cnt = 0;
}

void removeall(){ // Return link node to free store
while(head != NULL){
curr = head;
head = head->next;
delete curr;
}
}

public:
LList(int size=defaultSize){init(); } // Constructor

~LList(){removeall();} // Destructor

void printList() const{ // Print list content
assert(length()!=0 &&"Empty list");
Link<E>* temp = head->next;
while(true){
if(temp == tail){
std::cout << temp->element;
break;
}
std::cout << temp->element << " ";
temp = temp->next;
}
std::cout << "\n";
// temp不删除,最后指向的是tail指向的内存,不能释放.
};

void clear(){ removeall(); init(); } // Clear List

// Insert "it" at current position
void insert(const E& it){
curr->next = new Link<E>(it, curr->next);
if(tail == curr) tail = curr->next; // new tail
cnt++;
}

void append(const E& it){ // Append "it" to list
tail = tail->next = new Link<E>(it, NULL);
cnt++;
}

// Remove and return current element
E remove(){
assert(curr->next != NULL && "No element");
E it = curr->next->element; // Remember value
Link<E>* ltemp = curr->next; // Remember link node
if(tail == curr->next) tail = curr; // Reset tail
curr->next = curr->next->next; // Remove from list
delete ltemp; // Reclaim space
cnt--; // Decrement the count
return it;
}

void moveToStart(){ // Place curr at list start
curr = head;
}

void moveToEnd(){ // Place curr at list end
curr = tail;
}

// Move curr one step left; no change if already at front
void prev(){
if(curr == head) return;
Link<E>* temp = head;
// March down list until we find the previous element
while(temp->next != curr)temp = temp->next;
curr = temp;
}

// Move curr one step right; no change if already at end
void next(){
if(curr == tail) return;
curr = curr->next;
}

int length()const{
return cnt;
}

// Return the position of the current element
int currPos() const{
Link<E>*temp = head;
int i;
for(i=0; temp!=curr; i++){
temp = temp->next;
}
return i;
}

// Move down list to "pos" position
void moveToPos(int pos){
assert((pos>=0) && (pos<=cnt) && "Position out of range");
curr = head;
for(int i=0; i<pos; i++){curr = curr->next;}
}

const E& getValue() const{
assert(curr->next != NULL &&"No value");
return curr->next->element;
}
};



main.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

#include <iostream>
#include "ListADT.h"
#include "ListADT.cpp"

using namespace std;

int main() {
LList<int>L(100);
L.append(3);
L.append(4);
L.append(5);
L.printList();

return 0;
}

输出:

3 4 5

参考

Data Structures and Algorithms in C++

Data Structures and Algorithm Analysis in C++

本文标题:Singly Linked Lists

文章作者:不秩稚童

发布时间:2017年04月25日 - 00:06:17

最后更新:2017年08月13日 - 16:38:53

原始链接:http://datahonor.com/2017/04/25/Singly-Linked-Lists/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

击蒙御寇