CS162 - 6B - Review

TABLE OF CONTENTS

• Sections
  • Pointer
  • Dynamically allocated array
  • Linked List
    • Linked List operations
  • Data abstraction
  • Stack (LIFO)
  • Queue (FIFO)
  • Comparisions
    • Linked List and Array
• Notes
• Q&A
• Revision problems

Sections

Pointer

• CS161 - 1B

Dynamically allocated array

• CS162 - 1B/#array-allocation

Linked List

1. Singly Linked List
   • CS162 - 2B/#build-linked-list
   • CS162 - 3A
   • CS162 - 3B
2. Ordered Linked List
   • CS162 - 4A/#singly-ordered-linked-list
3. Doubly Linked List
   • CS162 - 4A/#double-linked-list
   • CS162 - 4B
4. Circular Linked List
   • CS162 - 5A
   • CS162 - 5B
   • CS162 - 5B (Bonus)

Linked List operations

• Create the list
• Display the list
• Remove the whole list
• Search an element in the list
• Insert a new item into the list
  • beginning
  • after x
  • before x
  • …
• Remove a node from the list

Data abstraction

• Data members
• Member functions

$\Rightarrow$ Struct

Stack (LIFO)

• CS162 - 6A/#stack

2 operations:

• push
• pop

If implementation based on SLL:

• push at the beginning of SLL.
• pop at the beginning of SLL.

Implementation

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

struct MyStack {
    Node* pHead = nullptr;
    
    void push(Node* pNew);
    Node* pop();
};

void MyStack::push(Node* pNew) {
    pNew->pNext = pHead;
    pHead = pNew;
}

Node* MyStack::pop() {
    if(!pHead) return pHead;
    Node* tmp = pHead;
    pHead = pHead->pNext;
    return tmp;
}

Full code (able to run): here

Queue (FIFO)

• CS162 - 6A/#queue

2 operations:

• enqueue
• dequeue

If the implementation is based on SLL:

• dequeue at the beginning of SLL
• enqueue at the end of SLL.

Implementation

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

struct MyQueue {
    Node* pHead = nullptr;
    Node* pTail = nullptr;
    
    void enqueue(Node* pNew);
    Node* dequeue();
};

void MyQueue::enqueue(Node* pNew) {
    if(!pHead) {
        pHead = pNew;
        pTail = pNew;
        pHead->pNext = nullptr;
    } else {
        pTail->pNext = pNew;
        pTail = pTail->pNext;
    }
}

Node* MyQueue::dequeue() {
    if(!pHead) return nullptr;
    Node* tmp = pHead;
    pHead = pHead->pNext;
    if(!pHead) pTail = nullptr;
    return tmp;
}

Full code (able to run): here

Comparisions

Linked List and Array

Notes

• Validity of pointer: pointing to null or not.
• Memory leaking: allocate $\Rightarrow$ deallocate.
• Doubly Linked List: algorithms have to be done the DLL way, don’t try to use the SLL approaches.

Q&A

Q1

1
2
3

int *pArr;
pArr = new int[n];
delete[] pArr;

Why not delete[n] pArr? How does the system know the number of elements to delete?

A1

The system stores the size somewhere. Where?

For some programming languages where arrays are “1-indexed”, they try to store the size in the 0-th element. But C++ arrays are “0-indexed”, where does the system store the size? Go home and find out!

Editor’s note:

delete[n] pArr was actually what people used to do. However, the system now stores its size, so you don’t have to (or rather, you can’t) explicitly tell the system how many elements to delete (it would be dangerous if you delete the wrong number of elements). You can still do delete[n] pArr nowadays, but n will be ignored by the compiler.

Now, where is the size of the array stored? Short answer: Magic (yes, the C++ Core Guidelines really said that).

The longer answer is that there are two popular methods, which you can read by clicking on the link to the C++ Core Guidelines above if you are interested.

Q2

Can we jump in the middle of an array and deallocate some of the elements but still use the un-deallocated elements?

A2

Unexpected result, we don’t know what will happen when we play around with the deallocation of the array. If you allocate the whole array, deallocate the whole array. You can still try deallocating in the middle of the array at your own risk.

Q3

What happens when you allocate 0 slots and delete 0 slots of an array? Is it okay?

int* a = new int[0];
delete[] a;

A3

The allocation is okay, and the deallocation is… okay too. If you forget to deallocate the 0-sized array,… no memory is leaking too, but for the standard implementation you should write out the deallocation, it’s a good practice.

Editor’s note

Forgetting to deallocate a 0-sized array can also lead to memory leak. It’s more than just a good practice to deallocate even a 0-sized array.

When you allocate an array of n elements, some compilers will actually allocate n + 1 elements: the extra element is for the size of the array. If you forget to delete the array, then this extra element will stay there the whole time.

Note that this behavior only applies for some compilers. If you return back to the Editor’s note on Q1, this is one of the magic methods to store the size of a dynamically allocated array.

Revision problems

Given a singly linked list, you are asked to build the following functions:

Print out the middle node. If the size of the SLL is odd, print the middle one. If the size of the SLL is even, print the left one.

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

int getNumNode(Node* pHead) {
    int res=0;
    Node* cur = pHead;
    while(cur) {
        res++;
        cur = cur->pNext;
    }
    return res;
}

void printMiddle(Node* pHead) {
    if(pHead = nullptr) {
        cout<<"Nothing";
        return;
    }
    int numNode = getNumNode(pHead);
    int mid = (numNode - 1) / 2;
    Node* cur = pHead;
    while(mid--) cur = cur->pNext;
    cout<<"Middle value is "<<cur->data;
}

Check if a given SLL is palindrome

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

bool isPalindrome(Node* pHead) {
    int n = getNumNode(pHead);
    int* arr = new int[n];
    
    for(int i=0; i<n; i++) {
        arr[i] = pHead->data;
        pHead = pHead->pNext;
    }
    int left = 0, right = n-1;
    while(left <= right) {
        if(arr[left] != arr[right]) {
            delete[] arr;
            return false;
        }
        left++; right--;
    }
    delete[] arr;
    return true;
}

There are a few more ways to implement the solution: