Singly Linked Lists

发表于 更新于 分类于 阅读次数： Valine：
初识

单链表的原理比较简单：单链表由一个个的节点组成，每个节点包含其要存储的数据和一个指针，其中指针指向下一个节点，由此串成一个单向的链表。容易算出，在非首部的任意位置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++