DATA STRUCTURES

• linear - sequential access - arrays, linked list
• non linear - non sequential access - tree, graph

complexity

arrays

• sequential search in linear time O(n) (order of n)

• binary search (sorted) in O(log n)

• bubble sort O(n^2)

• quick sort O(n^2)

• insertion sort O(n^2)

• merge sort O(n * log(n))

• disadvantages - fixed size

linked list

• linear

• each node connected by pointer

• double linked list - node contains pointer to next and previous node

• circular linked list - last node points to the first node

stack

• linear
• ordered
• lifo
• can be implemented using arrays and linked list

queue

• linear
• fifo
• can be implemented using arrays and linked list