I will do my best to make this a good reference for Anybody to study Data Structures I will split it into several steps.
The first thing in every step I will recommend for you a resources to study from. and I will try to write a good explanation and solve with you some problems.
- mycodeschool
- freeCodeCamp
- Arabic Competitive Programming(Arabic) DR.Mustafa Saad
- Mega Code(Arabic)
- Hard-Code(Arabic)
- Adel Nasim(Arabic)
- Paul Programming
- Step zero✅
First of all I have two questions what is Data Structure ? And Why do I want to study Data Structure?
- Data Structures - What and Why(Arabic) DR.Mustafa Saad
- What Are Data Structures? CS Dojo A data structure is a way of organizing data in the computer memory that we can use effectively.
You know that we store and reuse data in the memory, so we need fast and powerful algorithms to do that.
Now you may have a question how can we compare between algorithms to know the most useful algorithm in my case
I may have an algorithm that is so fast but take a lot of memory or in other case, you may have an algorithm so slow but take little memory or another one so fast and take little memoryWait for a second How can I compare between algorithms
So to compare between Algorithms One of the most fundamental ways to compare algorithms is to analyze their Time And Space complexity.
And this is some resources to know about Time And Space complexityFull course from freeCodeCamp
EducationAboutStuff
Adel Nasim (Arabic)
Search and you will find more and more
We will learn about the Implementation of the basic data structures.
Now you may have another question Why should I know something like that in case I can use the built-in data structure like STL in C++?
I will ask you a question what is better using these black boxes or knowing the implementation of them and having the ability to build your data structure?
The answer is YES you know the array
An array is a collection of items stored at contiguous memory locations. The idea is to store multiple items of the same type together. This makes it easier to calculate the position of each element by simply adding >an offset to a base value, i.e., the memory location of the first element of the array (generally denoted by the name of the array).
We talked about the most simple data structure The array data structure, But it's easy to see that the array is so limited by its initial size.
When the size is determined, it is fixed. So we aren't able to insert or remove elements that affect the size So we need something more flexible.
let's create our own dynamic array and we will call it vector. similar to STL Vector class in C++.If you don't know what is vector I recommend watching one of these videos :
- take U forward at 10:04
- Elzero Web School (Arabic)
- Adel Nasim (Arabic)
- Knowledge Center.
Now what we need in our class ??
....... We need Data and operations;
- I will talk about some Operations first .... We have some basic operations :
- set data
- get data
- insert data
- delete data
- find data by index
- For data: we can store our data in an array but wait it said that the array is limited so I will use a dynamic array
- How to do that? I will use pointers, int* which will point to an array and when I need another array I will make the pointer point to it and store data in the new array, and then
${\color{red}Delete}$ the old array.
I think Now you have a good background abohttps://media.geeksforgeeks.org/wp-content/cdn-uploads/20230726162542/Linked-List-Data-Structure.pngut vector and how our implementation will be So after you finish take a look at my code I think It would be helpful.
- Mega Code (Arabic)
- Neso Academy
Before Taking about linked list I will mention Important thing
There are broadly two types of Data structures: Linear and Non-linear. Linear data structures are those in which every element is connected to the previous element and the elements are present at a single level. Some examples of linear data structures are- Arrays, linked lists, stack,s and queues. Thus, a linked list is a linear data structure in which elements are not stored contiguously in the memory.
First of all we need to remember some things about array and vector
- Array is static. You can’t delete/insert/expand
- Vector was our way to get a dynamic array but if we want to add a new element in the vector and there is no free place we will take a new array and copy all the data = O(N).
So what if I want just to add the new element and I don't want to care about the size of the array? now we can talk about the linked list.
let's say that we have some variables how can we link them ?? what if every element points to the next one?
so the node is a structure that contains data and pointer points to the next node
struct node{
int data;
node *Next;
node(int data = 0) : data(data), Next(nullptr) {
}
~node(){
}
};
So in little words, we can say that a linked list is just a connection of some nodes, and another important component Head pointer points to the first node, and the Tail points to the last Node.
Traversal means visiting each node of the linked list. and we need to traverse the linked list to do operations like this.
- Insertion
- Deletion
- Display
- Search
- it's too easy to understand from this simple code.
node *ptr = head;
while (head != nullptr) {
std::cout << ptr->data << ' ';
ptr = ptr->Next;
}
when we talk about Insertion We talk about three cases.
-
Insertion at the beginning of the list
-
Insertion after a particular node.
-
Insertion at the end of the list
Insertion at the beginning means we will insert a node at the front of the list in the following way:
We can see that we have a linked list of the following elements: 10→20→30.
Once we insert a new node at the beginning, the list will be 50→10→20→30.
We need to traverse all the nodes before the position of insertion of the new node.
In this case, we will have a temporary pointer named ‘tmp’. This pointer tmp will be pointing to B because we need to insert E after ‘B’.
here we have a trick if we use the Tail pointer to point to the last node in the linked list it will be like Insertion at the beginning We just want to change the Tail pointer to point to the new node after changing the next pointer in the old last node to the new one.
but if we don't use a Tail pointer it will be like Insertion after a particular node.
Insertion operation | Complexity |
---|---|
At the beginning | O(1) |
After a particular node | O(n) |
At the end | O(n) |
At the end (using Tail) | O(1) |
Just like insertion, deletion also works in three different cases:
-
Deletion from beginning
-
Deleting a node other than the first and the last node
-
Deletion at the end
It involves deleting the first node of the linked list.
Suppose we initially had the linked list elements as 10→20→30→40.
If we perform the deletion of one node at the beginning, the linked list will be: 20→30→40.
Whenever we delete a node, we make the memory area occupied by that node free by using the Delete keyword. Otherwise, it might lead to a memory leakage problem.
If we have the address of a particular node, we can always delete the node next to it.
It is an easy case we can consider it like Deletion after a particular node.
Deletion operation | Complexity |
---|---|
At the beginning | O(1) |
After a particular node | O(n) |
At the end | O(n) |
Now try to implement and solve some problems using linked list.
Problem | Level | Solved | video |
---|---|---|---|
Reverse Linked List | ✅ | take U forward | |
Palindrome Linked List | ✅ | take U forward | |
Merge Two Sorted Lists | ✅ | ||
Linked List Cycle | ✅ | take U forward | |
Remove Nth Node From End of List | ✅ | take U forward | |
Reorder List | ✅ | ||
Add Two Numbers | ✅ | take U forward | |
Add Two Numbers II | ✅ |
- Neso Academy
- Hard-Code(Arabic) [18-21]
- Adel Nasim(Arabic)
In singly linked list We have single pointer pointing to the next node.
But a doubly linked list contains two pointers. One pointer points to the next node and one pointer to the previous node.
Every node in a doubly linked list has :-
- Data
- Address of the next node
- Address of the previous node
struct node{
int data;
node *next;
node *pre;
node(int data = 0) : data(data), next(nullptr), pre(nullptr) {
}
~node(){
}
};
so we can represent Double linked list like this :
Now let's Talk about simple operations on double Linked list : -
- Insertion
- Deletion
Insertion in a Linked List
Insertion in a linked list occurs at three different positions:
-
Insertion at the beginning of the list
-
Insertion after a particular node.
-
Insertion at the end of the list
We insert a node at the beginning such that the next pointer points to the node which was at first before. The previous pointer points to NULL.
Here, we have tried to insert M at the beginning.
void DoubleLinkedList::insert_front(int value) {
node *tmp = new node(value);
if (!head) {
head = tail = tmp;
} else {
link(tmp, head);
head = tmp;
}
length++;
}
Insertion after a particular node involves traversing all nodes before that node. We will make use of an extra pointer ‘temp’ for traversing the node up to a particular position.
here we want to add a node ‘M’ between node ‘B’ and node ‘C’.
If the list is empty, we will insert a node right after the Head. If the list is not empty, we first need to traverse the whole list to insert a node at the end of the list.
Here we are inserting M at the end.void insert_end(int value) {
node *tmp = new node(value);
if (!head) {
head = tail = tmp;
} else {
link(tail, tmp);
tail = tmp;
}
length++;
}
Deletion also works in three different cases:
-
Deletion from beginning
-
Deleting a node other than the first and the last node
-
Deletion at the end
It involves deleting the first node of the doubly linked list
void delete_front() {
if (!head) return;
head = head->next;
delete head->pre;
if (head)
head->pre = nullptr;
length--;
if (!length) {
tail = nullptr;
}
}
suppose we wish to delete node ‘C’ from the list having nodes: ‘A’, ‘B’, ‘C’ and ‘D’. Then, we will do it as follows:
void DoubleLinkedList::delete_at(int n) {
if (n == 1) {
delete_front();
} else if (n == length) {
delete_end();
} else {
node* temp = get_at(n); // to be deleted
node *pre = temp->pre;
node *nxt = temp->next;
pre->next = nxt;
nxt->pre = pre;
delete temp;
length--;
}
}
When the list has two or more nodes, we need to traverse the whole node and then delete the last node.
void delete_end() {
if (!head) return;
tail = tail->pre;
delete tail->next;
if (tail)
tail->next = nullptr;
length--;
if (!length) {
head = nullptr;
}
}
A stack is a linear data structure. It works on LIFO(Last in first out) or FILO(First in last out) approach. A stack contains a pointer named ‘top’. This pointer points to the top of the stack.
In stack, we can perform insertion and deletion operations at only one end i.e. at the top of the stack.
We can implement stack using array or using linked list
Stack {
private:
static const int MAX_SIZE = 100; // Maximum size of the stack
int stackArray[MAX_SIZE];
int top = -1; // Index of the top element
public:
Stack(); // Constructor
void push(int element); // Pushes an element onto the stack
int pop(); // Pops the top element from the stack
bool isEmpty(); // Checks if the stack is empty
};
To insert an element into the stack, we increment the top index and assign the element to the corresponding position in the stackArray.
void Stack::push(int element) {
if (top == MAX_SIZE - 1) {
// Stack is full
cout << "Stack Overflow!" << endl;
return;
}
stackArray[++top] = element;
}
To remove the top element from the stack, we decrement the top index.
void Stack::pop() {
if (top == -1) {
// Stack is empty
cout << "Stack Underflow!" << endl;
}
}
The linked list allocates memory dynamically. Thus, the stack will also have dynamic memory allocation. Since there is dynamic memory allocation, heap use comes into the picture. In the case of the linked list implementation, the stack will be considered full if the heap does not have enough space to create a new node. In a linked list, the last node points to NULL. if the stack is implemented using a linked list, its topmost node will also point to NULL.
In the stack Implementation, a stack contains a head pointer. where pushing and popping items happen at the head of the list. The first node has a null in the link field and second node-link has the first node address in the link field and so on and the last node address is in the “top” pointer.
Push Operation:
- Initialise a node
- Update the value of that node by data i.e. node->data = data
- Now link this node to the top of the linked list
- And update top pointer to the current node
Pop Operation:
- First Check whether there is any node present in the linked list or not, if not then return
- Otherwise make pointer let say temp to the top node and move forward the top node by 1 step
- Now free this temp node
Peek Operation:
- Check if there is any node present or not, if not then return.
- Otherwise return the value of top node of the linked list
Problem | Level | Solved | My code |
---|---|---|---|
Min Stack | ✅ |
Problem | Level | Solved | video |
---|---|---|---|
Invert Binary Tree | ✅ | ||
Maximum Depth of Binary Tree | ✅ | ||
Diameter of Binary Tree | ✅ | ||
Balanced Binary Tree | ✅ | ||
Same Tree | ✅ | ||
Leaf-Similar Trees | ✅ | ||
Subtree of Another Tree | ✅ | ||
Binary Tree Level Order Traversal | ✅ | ||
Binary Tree Right Side View | ✅ | ||
Pseudo-Palindromic Paths in a Binary Tree | ✅ | ||
Count Good Nodes in Binary Tree | ✅ | ||
Maximum Difference Between Node and Ancestor | ✅ | ||
Amount of Time for Binary Tree to Be Infected | ✅ | ||
Binary Tree Maximum Path Sum | ✅ |
Problem | Level | Solved | video |
---|---|---|---|
Range Sum of BST | ✅ | ||
Validate Binary Search Tree | ✅ |