Skip to main content Link Menu Expand (external link) Document Search Copy Copied

CS162 - 2B

TABLE OF CONTENTS

What will happen when you delete a pointer 2 times in a row?

1
2
3

int *p = new int;
delete p;
delete p;

This will crash. The first delete call will deallocate the data that p points to. Then, p still points to the same slot, but there’s nothing in that slot to delete, so the next delete call will crash the program.

However, if you delete the null pointer, either once or multiple times, nothing will happen. This is specified by the C++ Standard. You should always assign p to the null pointer immediately after deleting.

Now it’s time to build a simple linked list:

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

struct Node
{
    int data;
    Node* pNext;
};

Node* pHead;

//Add the first Node
pHead = new Node;
pHead->data = 1;
pHead->pNext = nullptr;

//Add the second Node
pHead->pNext = new Node;
pHead->pNext->data = 2;
pHead->pNext->pNext = nullptr;

//Add the third Node
pHead->pNext->pNext = new Node;
pHead->pNext->pNext->data = 3;
pHead->pNext->pNext->pNext = nullptr;

//Add the fourth Node
pHead->pNext->pNext->pNext = new Node;
pHead->pNext->pNext->pNext->data = 4;
pHead->pNext->pNext->pNext->pNext = nullptr;

//Add the n-th Node
pHead->...->pNext = new Node;
pHead->...->pNext->data = n;
pHead->...->pNext->pNext = nullptr;

As you can see, to add a new Node we need a lot of work to do, to make the work easier, we declare a pointer to help us:

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

Node* pHead;
Node* cur;

//Add the first Node
pHead = new Node;
cur = pHead;
cur->data = 1;
cur->pNext = nullptr;

//Add the second Node
cur->pNext = new Node;
cur = cur->pNext;
cur->data = 2;
cur->pNext = nullptr;

//Add the third Node
cur->pNext = new Node;
cur = cur->pNext;
cur->data = 3;
cur->pNext = nullptr;

//Add the fourth Node
cur->pNext = new Node;
cur = cur->pNext;
cur->data = 4;
cur->pNext = nullptr;

//Add the n-th Node
cur->pNext = new Node;
cur = cur->pNext;
cur->data = n;
cur->pNext = nullptr;

Student’s code

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

struct Node{
    int data;
    Node* pNext;
};

int main(){

    Node* pHead = nullptr;
    Node* cur = pHead;
    
    // Input the linked list
    while(true)
    {
        int x;
        cin>>x;
        if(x == 0) {
            //if (cur) cur->pNext = nullptr; 
            break;
        }
        
        if(pHead == nullptr) {
            pHead = new Node;
            cur = pHead;
        }
        else {
            cur->pNext = new Node;
            cur = cur->pNext;
        }
        
        cur->data = x;
        //cur->pNext = nullptr;
    }
    
    // Print the linked list
    for (cur = pHead; cur != nullptr; cur = cur->pNext)
    {
        cout << cur->data << endl;
    }
    
    // Delete the linked list
    for (cur = pHead; cur != nullptr;)
    {
        Node* next = cur->pNext;
        delete cur;
        cur = next;
    }
    pHead = nullptr;
}

Discussion:

Which assignment is better? line 17 or line 31

line 17 will run faster because it assign the nullptr value only once.

line 31 will safer because it ensure the structure of the linked list every time you add a new Node.

Teacher’s note

At line 12, we should not use the while(true) loop, the compiler will not know how to optimize your code, it’s not a good practice.

Teacher’s code

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

struct Node{
    int data;
    Node* pNext;
};

void inputLL(Node*& pHead);
void displayLL(Node* cur);
void deleteLL(Node*& pHead);

int main(){
    Node* pHead = nullptr;
    
    // Input the linked list
    inputLL(pHead);
    
    // Print the linked list
    displayLL(pHead);
    
    // Delete the linked list
    deleteLL(pHead);
    return 0;
}

void inputLL(Node*& pHead) 
{    
    int x;
    cout << "Please input the number: ";
    cin>>x;
    while(x != 0)
    {
        if(pHead == nullptr) {
            pHead = new Node;
            cur = pHead;
        }
        else {
            cur->pNext = new Node;
            cur = cur->pNext;
        }
        
        cur->data = x;
        cur->pNext = nullptr;
        cout << "Please input the number: ";
        cin>>x;
    }
}

void displayLL(Node* cur)
{
    for (; cur != nullptr; cur = cur->pNext)
    {
        cout << cur->data << endl;
    }
}

void deleteLL(Node*& pHead)
{
    while(pHead != nullptr)
    {
        Node* next = pHead->pNext;
        delete pHead;
        pHead = next;
    }
}