Basic data structures. Materiel Ases
- Transfer
Increasingly, I notice that modern self-taught people really miss the hardware. Everyone knows languages, but little basics, such as data types or algorithms. It is a little about data types.
Back in 1976, the Swiss scientist Niklaus Wirth wrote the book Algorithms + Data Structures = Programs.
40+ years later, this equation is still true. And if you are self-taught and go over the article for a long time in programming, you can diagonally. You can code the coffee.
The article will also have questions that you can hear at the interview.
The data structure is a container that stores data in a specific layout. This “layout” allows the data structure to be efficient in some operations and ineffective in others.
Linear elements form a sequence or a linear list, traversing nodes is linear. Examples: Arrays. Related list, stacks and queues.
Non-linear , if the traversal of nodes is non-linear, and the data is not consistent. Example: count and trees.
An array is the simplest and most widely used data structure. Other data structures, such as stacks and queues, are derived from arrays.
Image of a simple array of size 4 containing elements (1, 2, 3, and 4).
Each data element is assigned a positive numeric value (index), which corresponds to the position of the element in the array. Most languages define the initial array index as 0.
One-dimensional , as shown above.
Multidimensional , arrays inside arrays.
A stack is an abstract data type, which is a list of elements organized according to the LIFO principle (last in - first out, “the last to come - the first to go out”).
These are not arrays. This is the turn. He came up with Alan Turing.
An example of a stack would be a bunch of books arranged in a vertical order. In order to get a book that is somewhere in the middle, you will need to delete all the books placed on it. This is how the LIFO (Last In First Out) method works. The "Cancel" feature in applications works on LIFO.
The image of the stack, in three elements (1, 2 and 3), where 3 is at the top and will be removed first.
Like stacks, a queue - stores an item in a sequential manner. A significant difference from the stack is the use of FIFO (First in First Out) instead of LIFO.
An example of a queue is a queue of people. The last one was ranked last and you will be, and the first one will leave her first.
The image of the queue, in four elements (1, 2, 3 and 4), where 1 is at the top and will be deleted first
A linked list is an array where each element is a separate object and consists of two elements — data and a link to the next node.
A fundamental advantage over an array is structural flexibility: the order of the elements of a linked list may not coincide with the order of the data elements in computer memory, and the order of traversing a list is always explicitly defined by its internal connections.
Unidirectional , each node stores the address or link to the next node in the list, and the last node has the following address or link as NULL.
1-> 2-> 3-> 4-> NULL
Bidirectional , two links associated with each node, one of the strong points to the next node and one to the previous node.
NULL <-1 <-> 2 <-> 3-> NULL
Circular , all nodes are connected to form a circle. At the end there is no null. A cyclic linked list can be a single or double cyclic linked list.
1-> 2-> 3-> 1
The most frequent, linear unidirectional list. An example is the file system.
A graph is a set of nodes (vertices) that are connected to each other in the form of a network by edges (arcs).
Oriented , the edges are directional, i.e. there is only one available direction between two connected vertices.
Non-oriented , to each of the edges, you can make the transition in both directions.
Mixed
A tree is a hierarchical data structure consisting of nodes (vertices) and edges (arcs). Trees are essentially linked graphs without cycles.
Tree structures everywhere. The tree of skills in the games everyone knows.
Simple Tree Tree
Types
Binary tree is the most common.
“A binary tree is a hierarchical data structure in which each node has a value (it is also a key in this case) and references to the left and right descendant. "- Procs
Variety of tree for strings, quick search. Dictionaries. T9.
This is how such a tree stores the words “top”, “thus” and “their”.
Words are stored from top to bottom, green colored nodes “p”, “s” and “r” indicate the end of “top”, “thus” and “their”, respectively.
Hashing is a process used to uniquely identify objects and store each object in a pre-calculated unique index (key).
The object is stored as a key-value pair, and the collection of such elements is called a “dictionary”. Each object can be found using this key.
In essence, this is an array in which the key is represented as a hash function.
Hashing performance depends on
An example of hash mapping in an array. The index of this array is calculated through a hash function.
The materiel is as interesting as the languages themselves. Perhaps someone will see the familiar basic structures and be interested.
Thanks for reading. I hope not to waste time =)
PS: I am sorry, as it turned out, the translation of the article was already here and very recently, I overlooked it.
If interested, here it is , thanks to Hokum , I will be more careful.
Back in 1976, the Swiss scientist Niklaus Wirth wrote the book Algorithms + Data Structures = Programs.
40+ years later, this equation is still true. And if you are self-taught and go over the article for a long time in programming, you can diagonally. You can code the coffee.
The article will also have questions that you can hear at the interview.
What is a data structure?
The data structure is a container that stores data in a specific layout. This “layout” allows the data structure to be efficient in some operations and ineffective in others.
What are the?
Linear elements form a sequence or a linear list, traversing nodes is linear. Examples: Arrays. Related list, stacks and queues.
Non-linear , if the traversal of nodes is non-linear, and the data is not consistent. Example: count and trees.
Basic data structures.
- Arrays
- Stacks
- Queues
- Related Lists
- Counts
- Trees
- Prefix trees
- Hash table
Arrays
An array is the simplest and most widely used data structure. Other data structures, such as stacks and queues, are derived from arrays.
Image of a simple array of size 4 containing elements (1, 2, 3, and 4).
Each data element is assigned a positive numeric value (index), which corresponds to the position of the element in the array. Most languages define the initial array index as 0.
There are
One-dimensional , as shown above.
Multidimensional , arrays inside arrays.
Basic operations
- Insert-insert an element at a given index
- Get-returns an element at a given index
- Delete-delete an item at a given index
- Size-get the total number of elements in the array
Questions
- Find the second minimal element of the array
- The first non-repeating integers in an array
- Merge two sorted arrays
- Reorder positive and negative values in an array
Stacks
A stack is an abstract data type, which is a list of elements organized according to the LIFO principle (last in - first out, “the last to come - the first to go out”).
These are not arrays. This is the turn. He came up with Alan Turing.
An example of a stack would be a bunch of books arranged in a vertical order. In order to get a book that is somewhere in the middle, you will need to delete all the books placed on it. This is how the LIFO (Last In First Out) method works. The "Cancel" feature in applications works on LIFO.
The image of the stack, in three elements (1, 2 and 3), where 3 is at the top and will be removed first.
Basic operations
- Push-insert element on top
- Pop returns the top item after removing from the stack.
- isEmpty-returns true if the stack is empty
- Top returns the top item without removing it from the stack.
Questions
- Implement a queue with a stack
- Sorting values in the stack
- Implement two stacks in an array
- Reverse Row with Stack
Queues
Like stacks, a queue - stores an item in a sequential manner. A significant difference from the stack is the use of FIFO (First in First Out) instead of LIFO.
An example of a queue is a queue of people. The last one was ranked last and you will be, and the first one will leave her first.
The image of the queue, in four elements (1, 2, 3 and 4), where 1 is at the top and will be deleted first
Basic operations
- Enqueue—) - inserts the item at the end of the queue
- Dequeue () - removes an item from the front of the queue
- isEmpty () - returns true if the queue is empty
- Top () - returns the first element in the queue.
Questions
- Implement stack using queue
- Reverse of the first N queue items
- Generating binary numbers from 1 to N using a queue
Related list
A linked list is an array where each element is a separate object and consists of two elements — data and a link to the next node.
A fundamental advantage over an array is structural flexibility: the order of the elements of a linked list may not coincide with the order of the data elements in computer memory, and the order of traversing a list is always explicitly defined by its internal connections.
There are
Unidirectional , each node stores the address or link to the next node in the list, and the last node has the following address or link as NULL.
1-> 2-> 3-> 4-> NULL
Bidirectional , two links associated with each node, one of the strong points to the next node and one to the previous node.
NULL <-1 <-> 2 <-> 3-> NULL
Circular , all nodes are connected to form a circle. At the end there is no null. A cyclic linked list can be a single or double cyclic linked list.
1-> 2-> 3-> 1
The most frequent, linear unidirectional list. An example is the file system.
Basic operations
- InsertAtEnd - Inserts the specified item at the end of the list
- InsertAtHead - Insert an item at the top of the list
- Delete - removes the specified item from the list.
- DeleteAtHead - deletes the first list item
- Search - returns the specified item from the list
- isEmpty - returns True if the linked list is empty
Questions
- Reverse linked list
- Defining a cycle in a linked list
- Return N item from end in linked list
- Remove duplicates from linked list
Counts
A graph is a set of nodes (vertices) that are connected to each other in the form of a network by edges (arcs).
There are
Oriented , the edges are directional, i.e. there is only one available direction between two connected vertices.
Non-oriented , to each of the edges, you can make the transition in both directions.
Mixed
Found in such forms as
- Adjacency matrix
- Adjacency list
General graph traversal algorithms
- Search wide - bypass by level
- Search in depth - traversing vertices
Questions
- Implement the search in width and depth
- Check whether the graph is a tree or not
- Count the number of edges in the column
- Find the shortest path between two vertices
Trees
A tree is a hierarchical data structure consisting of nodes (vertices) and edges (arcs). Trees are essentially linked graphs without cycles.
Tree structures everywhere. The tree of skills in the games everyone knows.
Simple Tree Tree
Types
- N tree
- Balanced tree
- Binary tree
- Binary Search Tree
- Avl tree
- 2-3-4 trees
Binary tree is the most common.
“A binary tree is a hierarchical data structure in which each node has a value (it is also a key in this case) and references to the left and right descendant. "- Procs
Three ways to traverse the tree
- In direct order (top to bottom) - the prefix form.
- In symmetrical order (from left to right) - infix form.
- In the reverse order (bottom to top) - the postfix form.
Questions
- Find the height of the binary tree
- Find N smallest item in binary search tree
- Find nodes at a distance N from the root
- Find the ancestors of the N node in the binary tree
Trie (prefix tree)
Variety of tree for strings, quick search. Dictionaries. T9.
This is how such a tree stores the words “top”, “thus” and “their”.
Words are stored from top to bottom, green colored nodes “p”, “s” and “r” indicate the end of “top”, “thus” and “their”, respectively.
Questions
- Count the total number of words
- Print all words
- Sort array elements from the prefix tree
- Creating a T9 dictionary
Hash table
Hashing is a process used to uniquely identify objects and store each object in a pre-calculated unique index (key).
The object is stored as a key-value pair, and the collection of such elements is called a “dictionary”. Each object can be found using this key.
In essence, this is an array in which the key is represented as a hash function.
Hashing performance depends on
- Hash Functions
- Hash Size
- Methods of dealing with collisions
An example of hash mapping in an array. The index of this array is calculated through a hash function.
Questions
- Find symmetric pairs in an array
- Find if the array is a subset of another array
- Describe open hashing
Resource list
- medium.freecodecamp.org/the-top-data-structures-you-should-know-for-your-next-coding-interview-36af0831f5e3
- www.geeksforgeeks.org/commonly-asked-data-structure-interview-questions-set-1
- prog-cpp.ru/data-list
- habr.com/post/267855
- habr.com/post/273687
- habr.com/post/150732
- ruhighload.com/%D0%A7%D1%82%D0%BE+%D1%82%D0%B0%D0%BA%D0%BE%D0%B5+%D1%85%D0%B5%D1%88-% D1% 82% D0% B0% D0% B1% D0% BB% D0% B8% D1% 86% D1% 8B +% D0% B8 +% D0% BA% D0% B0% D0% BA +% D0% BE% D0% BD% D0% B8 +% D1% 80% D0% B0% D0% B1% D0% BE% D1% 82% D0% B0% D1% 8E% D1% 82
- ru.wikipedia.org
Instead of conclusion
The materiel is as interesting as the languages themselves. Perhaps someone will see the familiar basic structures and be interested.
Thanks for reading. I hope not to waste time =)
PS: I am sorry, as it turned out, the translation of the article was already here and very recently, I overlooked it.
If interested, here it is , thanks to Hokum , I will be more careful.