Basic Data Structures — Collections
The field of Data Structures is one of the most important fields in computer science. The basic of Data Structures are collection base DS(Data Structure) Collection are containers used to store data in order to access it and use it in the future. Examples for collections are lists arrays dictionary etc.
Lists
In theory a list is a collection of related objects that have with no fixed length.
Array:
A list of elements one after another that have an index (an index is just the number associated with a place in the array).
Why does this data structure exist?
To store a list of things and to read the data by indexes efficiently. Pros read the data, and find to find the net element takes O(1). If you are not familiar with the expression O() here is a FREE article that explain the concept in depth. Cons insertion and deletion takes O(n) — because every time we change the array we need to shift every element (in the worst case senior).
Use in projects: for storage data which I don’t want to modify and change, but only to read.
What is this DS optimized for? read data that you stored and don’t want to change.
Array’s big O chart:
Linked List:
A list that every element saves it’s next element (pointers)
Why does this data structure exist?
To add delete and insert your data — Change the stored data. Pros Very good with messing with the data O(1). Cons Access and search takes O(n) — there is no fixed order to the list.
Use in projects: To storage data that I want to have reference for each next element — maze algorithm.
What is this DS optimized for? Creating nodes that need to be logically connected by reference and not by index.
Linked List big O chart:
TIP: there is a developed type of linked list called doubly linked list. doubly linked list reference for the next and previous element — the only change is that you can traversed(go throw) the list in both directions.
Stack:
A list that stores the element one on another First In Last Out — F.I.L.O. — like a stack of books.
Why does this data structure exist?
For saving the history of the data you want to store . Recursion, backtracking algorithm — (Maze Generators), keep track of state or when things have occurred. Pros Very good with finding the last element that you added O(1). Cons Can’t access the middle elements of the stack.
Use in projects: To save history of my server log + backtracking — reversing a list. In errors the bubbling process keeps track by the stack.
What is this DS optimized for? To access recently used data. The order you used the data. Keep track of state order.
Stack big O chart:
Queue:
Data structure that works like a line of people to get pancakes — First in First Out F.I.F.O.
Why does this data structure exist?
Great at storing the order of things that need to happen. A server that gets a lot of requests to connect can store the requests in a queue, that way it’s going to connect to the first ones who asked thus dequeuing. Pros Very good with dealing at the oldest element in the queue O(1). Cons Can’t access the middle elements of the queue.
Use in projects: To deal with requests at a server. Because I can implement the priority queue and that way handling the most urgent data. + at my assistance, will alert me first of the urgent stuff and the oldest.
What is this DS optimized for? To access the most needed data. Alerts and time schedules.
Queue big O chart:
Queues types:
Dequeues is a queue that you can enqueue and dequeue in both sides of the queue. Priority Queue is a queue that each element has a priority field, when you dequeue you do it first to the biggest priority element. And enqueue the element with a priority field. — can be implemented with heap, binary tree or linked list.
