Scribd
Upload
30 views1 page

Week 5 Data Structures

The document discusses several common data structures: queues, stacks, linked lists, trees, dictionaries, and tries. Queues follow a FIFO model for adding and removing items while stacks use LIFO. Linked lists store data and addresses non-contiguously allowing flexible insertion. Binary search trees provide sorted storage and searching in O(logn) time while hashing maps keys to values in arrays for fast O(1) retrieval. Tries store strings as tree nodes for extremely fast O(1) string operations but use significant memory.

Uploaded by

tanijain1501
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as TXT, PDF, TXT or read online on Scribd
30 views1 page

Week 5 Data Structures

The document discusses several common data structures: queues, stacks, linked lists, trees, dictionaries, and tries. Queues follow a FIFO model for adding and removing items while stacks use LIFO. Linked lists store data and addresses non-contiguously allowing flexible insertion. Binary search trees provide sorted storage and searching in O(logn) time while hashing maps keys to values in arrays for fast O(1) retrieval. Tries store strings as tree nodes for extremely fast O(1) string operations but use significant memory.

Uploaded by

tanijain1501
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as TXT, PDF, TXT or read online on Scribd

Data Structures

abstract data structure-

1. queue - FIFO // at airport, todo-list


enqueue - adding at end of the queue
dequeue - adding and removing can done from both front or end.

2. stack - LIFO // books , trays, gmail


push - add to top of stack
pop - delete to top of stack

insertion - O(1)

size - of stack
capacity - of memory

array - contiguous memory --- when we awant to add something then it can't happen
in array due to size constriction and it become inefficient.

realloc - memory allocation better then malloc.

memory leak

3. linked lists(ll) - data and address(pointing to next data) // they are not
contiguous memory.
for(node *ptr = list;ptr!=NULL;ptr=ptr->next)

searching in ll - O(n)
insertion in ll - O(1)

4. trees -
1. binary search trees - sorted tree , root - left subtree - right subtree // we
are using more memory here. -- it has to be balanced. -- O(logn)

5. dictionary - key-value pairs


HASHING - algorithm like dict -- hash tables - array , pointer.-- O(n) but faster

6. Trie -- O(1) -- tree each of whose nodes are array. -- as all lengths are finite
means they take contant time. -- disad -- lots of memory.--------
it depend only on the length on input give contant time in all operations.

You might also like