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

CS162 - 5A

Proofread by Huỳnh Hà Phương Linh

TABLE OF CONTENTS

Introduction - Circular Linked List

Circular Linked List is similar to SLL but the pNext of the last node points to the first node. Thus, if the CLL has only one node, that single node’s pNext will point to itself.

Problem statements

  1. Find x
    Node* findX(Node* pFirst, int x);
  2. Remove the $1^{st}$ x
    void remove1stX(Node* &pFirst, int x);
  3. Remove all x s
    void removeAllXs(Node* &pFirst, int x);

Problem 1

Student’s code

1
2
3
4
5
6
7
8
9
10
11

Node* findX(Node* pFirst, int x) {
    Node* cur=pFirst;
    if(pFirst == nullptr)
        return nullptr;
    while(cur->data != x && cur->pNext != pFirst) {
        cur = cur->pNext;
    }
    if(cur->data == x)
        return cur;
    return nullptr;
}

Discussion

THE FIRST ACCEPTED CODE WRITEN BY Ô HỚN SÂM.

Problem 2

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

void remove1stX(Node* &pFirst, int x) {
    if(pFirst == nullptr) return;
    if(pFirst->pNext == pFirst) {
        if(pFirst->data == x) {
            delete pFirst;
            pFirst = nullptr;
        }
        return;
    }
    
    Node* cur = pFirst;
    while(cur->pNext->data != x &&
         cur->pNext->pNext != pFirst) {
        cur = cur->pNext;
    }
    if(cur->pNext->data == x) {
        Node* tmp = cur->pNext;
        cur->pNext = cur->pNext->pNext;
        if(tmp == pFirst) pFirst = tmp->pNext;
        delete tmp;
    }
}

Discussion

  • The code doesn’t delete the first node (if statement at line 12-13).
  • If there are multiple nodes with value x and pFirst is the first one, the second node will be deleted instead.

Fixed 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

void remove1stX(Node* &pFirst, int x) {
    if(pFirst == nullptr) return;
    if(pFirst->data == x) {
        Node* pLast = pFirst;
        while(pLast->pNext != pFirst) 
            pLast = pLast->pNext;
        
        if(pLast == pFirst) {
            delete pFirst;
            pFirst = nullptr;
            return;
        }
        
        pLast->pNext = pFirst->pNext;
        delete pFirst;
        pFirst = pLast->pNext;
        return;
    }
    
    Node* cur = pFirst;
    while(cur->pNext->data != x &&
         cur->pNext->pNext != pFirst->pNext) {
        cur = cur->pNext;
    }
    if(cur->pNext->data == x) {
        Node* tmp = cur->pNext;
        cur->pNext = cur->pNext->pNext;
        delete tmp;
    }
}

Problem 3

Student’s code (Fixed)

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

void removeAllXs(Node* &pFirst, int x) {
    if(!pFirst) return;
    Node* cur = pFirst;
    while(cur->pNext != pFirst) {
        if(cur->pNext->data == x) {
            Node* tmp = cur->pNext->pNext;
            delete cur->pNext;
            cur->pNext = tmp;
        }
        else cur = cur->pNext;
    }
    if(cur->pNext->data == x) {
        Node* tmp = cur->pNext->pNext;
        if(cur->pNext == pFirst) pFirst = tmp;
        if(pFirst->pNext == pFirst)
            pFirst = nullptr;
        delete cur->pNext;
        cur->pNext = tmp;
    }
}

Discussion

  • Time is running out so we couldn’t discuss much. The code works just fine.