linked lists the insertion and deletion routines are similar to those in single-ended list howeverboth insertion routines must watch out for the special case when the list is empty prior to the insertion that isif isempty(is truethen insertfirst(must set last to the new linkand insertlast(must set first to the new link if inserting at the beginning with insertfirst()first is set to point to the new linkalthough when inserting at the end with insertlast()last is set to point to the new link deleting from the start of the list is also special case if it' the last item on the listlast must be set to point to null in this case unfortunatelymaking list double-ended doesn' help you to delete the last link because there is still no reference to the next-to-last linkwhose next field would need to be changed to null if the last link were deleted to conveniently delete the last linkyou would need doubly linked listwhich we'll look at soon (of courseyou could also traverse the entire list to find the last linkbut that' not very efficient linked-list efficiency insertion and deletion at the beginning of linked list are very fast they involve changing only one or two referenceswhich takes ( time findingdeletingor inserting next to specific item requires searching throughon the averagehalf the items in the list this requires (ncomparisons an array is also (nfor these operationsbut the linked list is nevertheless faster because nothing needs to be moved when an item is inserted or deleted the increased efficiency can be significantespecially if copy takes much longer than comparison of courseanother important advantage of linked lists over arrays is that linked list uses exactly as much memory as it needs and can expand to fill all of available memory the size of an array is fixed when it' createdthis usually leads to inefficiency because the array is too largeor to running out of room because the array is too small vectorswhich are expandable arraysmay solve this problem to some extentbut they usually expand in fixed-sized increments (such as doubling the size of the array whenever it' about to overflowthis solution is still not as efficient use of memory as linked list abstract data types in this section we'll shift gears and discuss topic that' more general than linked listsabstract data types (adtswhat is an adtroughly speakingit' way of looking at data structurefocusing on what it does and ignoring how it does its job