COMP 2140 Lecture 7: 09_26_list.pdf
13 Aug 2014
School
Department
Course
Professor
Document Summary
An order list of positive 6-digit integer (000000 to 999999) Make the last node points to the 1st one (instead of null) We can reach entire list starting from any node. Allow easy access to both ends of a list have reference pointing to the last node. Solution: a dummy node top will never be null node cannot point to itself (except dummy) Insert and delete items at both ends in constant running time. E. g. delete the node at the end of list (at least 2 items in dlist) You can use dummy nodes with doubly-linked list as well point to itself prev. Delete node at the end head. prev. prev. next = head; head. prev = head. prev. prev; Consider special cases (front of list, end of list, empty list, ) equality) But it is in place on linked lists. Linked lists can be used in radix sort to store numbers each bucket. You cannot do binary search on sorted linked lists.
