Linked List Intro

Linked Lists start with space of just one allocated element and add on new elements easily without the need to do any copying and reallocating.

Linked Lists ADT

The following operations make linked lists an ADT:

Main Linked Lists Operations

• Insert: inserts an element into the list
• Delete: removes and returns the specified position element from the list

Auxiliary Linked Lists Operations

• Delete List: removes all elements of the list (disposes the list)
• Count: returns the number of elements in the list
• Find nth node from the end of the list

• Main Disadvantage of linked lists is access time to individual elements.
• Linked lists take O( n) for access to an element in the list in the worst case.
• linked lists are hard to manipulate. If the last item is deleted, the last but one must then have its pointer changed to hold a NULL reference. This requires that the list is traversed to find the last but one link, and its pointer set to a NULL reference.
• linked lists waste memory in terms of extra reference points.
• One of the biggest advantages of linked lists over arrays is that inserting an element at any location takes only O( 1) time. However, it takes O( n) to search for an element in a linked list.