Computer Science CS50 Lecture Notes - Linked List, Insertion Sort, Graham Scan
2 Jul 2022
School
Department
Course
Professor
Document Summary
Linked list: maintain pointer to first node in a linked list; insert/remove from front. Array: use array s[] to store n items on stack. Underflow: throw exception if pop from an empty stack. Holding a reference to an object when it is no longer needed. https://cs. ericyy. me/algorithms-1/week-2/index. html. Already pop up the n-th item, should set it null before return. Resizing array stack push(): double size of array s[] when array is full. pop(): halve size of array s[] when array is one-quarter full. Linked list: maintain pointer to first and last nodes in a linked list; Use array q[] to store items in queue. enqueue(): add new item at q[tail]. dequeue(): remove item from q[head]. In iteration i, find index min of smallest remaining entry. Assume left side is already sorted, then in iteration i, swap a[i] to the left if a[i] < a[i-1] Move entries more than one position at a time by h-sorting the array. https://cs. ericyy. me/algorithms-1/week-2/index. html.
