Category Archives: 未分類

Merit & Demerit of each basic data construction

Array:

– Efficient for adding or reading element into array, if know the location for these operations

– Takes more time to find a element and delete one

– Fixed size

 

Ordered Array:

– Save more time than unordered array for finding element

– Takes more time to add or delete

– Fixed size

 

Stack:

– Extremely easy to output elements in the opposite order thanks to the LIFO

– Cause of the LIFO same, if we want to add or delete a element in stack, it is nessesary to pop the elements above it first which makes add and delete operation very inefficient

 

Queue:

– FIFO which differs from stack

– In the same way, add and delete operations are inefficient

– Suitable for program that needs only push elements in order and pop them in the same order

 

List:

– Elements are oreded by pointers which makes add and delete operation very fast cause it isn’t nessesary to move other elements

– When do find operation, it takes more time because we can only find a element’s address by reading the pointer writen into the previous element

 

Tree:

– Efficient for all of the add, delete and find operations

– Complicated algorithm

– Every node includes pointers for children and even parents which sacrifices memory space

– Efficience will be affected if tree is not balanced which will be solved in Red-black tree or 2-3-4 tree

 

Hash:

– Extremely efficient for add and find operation if key value is known

– Inefficient delete operation

– Efficience for add and find operation will be very low if key value is unkown

 

Map:

– Enable for complicated construction including relationship similar with reality

– Some algorithms are very inefficient and complicated