COMS W3134 Chapter Notes - Chapter 3: Doubly Linked List, Linked List, Time Complexity
25 Oct 2016
School
Department
Course
Professor
Document Summary
Set of objects together with a set of operations, mathematical abstractions: objects such as lists, sets, graphs and their operations, operations such as add, remove, contains. 3. 2 the list adt: popular operations are printlist and makeempty, find, insert, remove, findkth. Simple array implementation of lists: e. g. an array arr, which initially has length 10, can be expanded as needed, worst case for these operations is o(n, need to avoid linear cost of insertion and deletion. If change is to be made, inserting or removing an item form a linked list does not require moving lost of items and only involves a constant number of changes to node links. 3. 3 lists in the java collections api: collection interface, collections api lives in package java. util, collection stores collection of identically typed objects, abstracted in collection interface, methods include size, isempty, add, remove, collection interface extends iterable interface.
