DSA_01

---

Just a note

Linked List:

Insert:

Insert First:

1. Kiểm tra memory ở heap còn cáp thêm được node mới không
2. Nối bình thường, dùng this->head

Insert Last:

1. Kiểm tra memory ơ heap còn cấp thêm được node mơi không
2. Kiểm tra empty List: (vì nêu empty, head đang là NULL, không thê trỏ head->next). Nếu empty -> insertFirst, nếu không cho pTemp chạy.
3. Không free pTemp: vì pTemp lưu ở stack, hết hàm sẽ free, vùng heap của pTemp trỏ đến lây tư vùng heap của head, vùng này thuộc linked list không thê free. hay nói cách khac pTemp chỉ mượn vùng heap có sẵn chứ không dùng vùng heap nào mới.
4. pTemp = NULL;

Insert Position:

1. Kiểm tra memory ở heap còn câp thêm được node mới không
2. Kiểm tra position insert: nêu = 0 => insertFirst; nêu = this->count => insertLast, nếu năm giữa cho pTemp chạy tư 1 tới < position, nếu không return.

Delete:

Delete First:

1. Check empty list
2. pTemp cho this->head, free pTemp
3. pTemp = NULL;

Delete Last:

1. Check empty list
2. Check 1 member list => DeleteFirst
3. Tạo 1 pTemp = head và 1 pTempNext = pTemp->next. Cho cả 2 chạy đến khi pTempNext = NULL, xóa pTempNext, gán pTemp->next = NULL.
4. pTemp = NULL, pTempNext = NULL

Delete Position:

1. Check empty list
2. Check position == 0 => DeleteFirst();
3. Check position > 0 && position < this->count => chạy pTemp tư 1 tới < position. pTemp sẽ dừng ngay trước node cân xóa, tạo pTempNext = pTemp->next , gán pTemp = pTemp->next->next và free pTempNext.
4. Trỏ pTemp và pTempNext vê NULL để tránh dangling pointer.

Pointer vs Object variable:

void main(){
    LinkedList *p = new LinkedList();
    p->InsertLast(20);
    // do sth with p here
    func(p);
    delete p;
}

void main(){
    LinkedList ob;
    ob.InsertLast(20);
    // do sth with ob here
    func(ob);
}

Hay

void func(LinkedList *a){
    a->InsertFist(10);
}

void func(LinkedList myOb){
    myOb.InsertFist(10);
}

https://www.learncpp.com/cpp-tutorial/79-the-stack-and-the-heap/ https://stackoverflow.com/questions/38803949/why-use-dynamic-memory-allocationi-e-malloc-when-implementing-linked-list-i Khi nào? Cái gì?