CS 225 Lecture Notes - Lecture 15: Doubly Linked List, Linked List, Skip List
28 Sep 2016
School
Department
Course
Professor
Document Summary
Abstract data type (adt) - not specified in any particular language template class list { public: ~list(); int getsize() const; void insert(int loc, lit e); void remove(int loc); // like a static array -> linked lists listnode * head; int size; listnode * find(listnode * place, int k); struct listnode. // constructor for struct listnode(lit newdata): data(newdata), next(null) >[3][->] [6][->] [4][null] void list::insert(int k, lit e) { listnode * t = new listnode(e); if(k == 1) insertatfront(e); else { // k-1 because it"s index 1, and e should be the kth node listnode * p = find(head, k-2); t->next = p->next; p->next = t; // we assume the array is big enough to shift all the data ahead of time. insert new kth in array: O(n) to find, depends on list or number of elements. O(n) for shift, depends on list or number of elements. Insert new node in kth position with sentinel:
