Transcript LinkList

CSCI-255
LinkedList
Review Basic Data Structures
Related to Linked List
• Array contiguous, fixed size at compile time,
int a[10];
• Dynamic array: contiguous, size not fixed at
compile time. However, to increase the size at
run time, the whole block of memory has to
be created, and the whole block of data in the
original dynamic array will be copied to the
new dynamic array
int *a;
int size;
cin>> size;
Linked Lists vs. Arrays
• Linked Lists differ from arrays because they
don’t have a fixed size but like arrays can only
store elements of the same type
• Main advantage over arrays is easy insertion
and deletion of nodes
• A well defined list may be the basis for the
implementation of several other data
structures such as queues, stacks, trees, and
graphs
Lists as ADTs
• Data
– A collection of elements of the same type
• Operations
–
–
–
–
–
–
–
–
–
IsEmpty
IsFull
Length
Insert
Delete
IsPresent
Print
SortedList
…
Two Options to Implement List
• Option 1: Use a dynamic array stored in
contiguous memory locations, implementing
operations Insert and Delete by moving list
items around in the array, as needed
• Option 2: Use a linked list (to avoid excessive
data movement from insertions and deletions)
not necessarily stored in contiguous memory
locations
Self-referential Data Types
info
next
Linked List
• A linked list is a list in which the order of the
components is determined by an explicit link
member in each node
• Each node contains a component member
and also a link member that gives the
location of the next node in the list
• An external pointer (or head pointer) points
to the first node in the list
Linked List (cont’d)
• Nodes can be located anywhere in memory
• The link member holds the memory address
of the next node in the list
Insertion at the Beginning of the List
Insertion at the Beginning of the List
(cont’d)
Time Complexity?
Insertion at the End of the List
Insertion at the End of the List (cont’d)
Time Complexity?
Time Complexity if no tail (i.e., only head)?
Deletion from the Beginning of the List
Deletion from the Beginning of the List
(cont’d)
Time Complexity?
What if the list is empty?
Deletion from the End of the List
Deletion from the End of the List (cont’d)
Time Complexity?
What if the list is empty?
Deleting from Anywhere in the List
Deleting from Anywhere in the List (cont’d)
Deleting from Anywhere in the List
(cont’d)
• Best case time complexity?
• Worst case time complexity?
• Average case time complexity? (done in class)
Comparison: Array, Dynamic
Array, LinkedList
Index Insert Insert
ing
at the at the
beginn end
ing
Delete Delete
at the at the
beginn end
ing
O(1)
N/A
N/A
N/A
N/A
Dynamic O(1)
Array
O(n)
O(1)
O(n)
O(1)
O(n)
LinkedLi
st (with
head)
O(n)
O(1)
O(n)
O(1)
O(n)
O(n)
LinkedLi
st (with
head
and tail)
O(n)
O(1)
O(1)
O(1)
O(1)
O(n)
Array
Insert/
Delete
in the
middle