28 posts tagged with "datastructures"

A ring buffer is a data structure that works similar to a queue. Why similar? From the principle it is a queue, the difference to normal queues is that these have a fixed size in the normal case. A ring buffer works according to the FIFO principle like the queue.

InsertionSort is a sorting method which is easy to implement. InsertionSort works on the principle that you go through the array to be sorted and compare each element with its predecessor. You start at the 2nd element in the array.

A stack is a data structure which is used in many areas, e.g. in CPUs, in network technology under Linux(TCP/IP stack), or also generally with other algorithms like e.g. PDAs, depth search in graphs, etc....

The Big-O notation, many talk about it but what is it? It is the question, how fast is the code, which you have in front of you. You have an algorithm that is supposed to solve a task, all well and good, but how long does it take? And more importantly, how does it look with a lot of data?

Linked lists, or single or double linked lists, are data structures that represent dynamic lists. The data structure is fundamental and consists of two classes, the list and the nodes.

Hashing is a data structure which allows to add and read data with $O(1)$. But the search is done with $O(n)$.

Quicksort is a sorting method according to the principle "divide and conquer" with an effort in best case $O(n Log(n))$ in avg case $O(n Log(n))$ and in worst case $O(n^2)$

Mergesort is a sorting method to sort relatively fast huge amounts of data. Mergesort belongs to the divide & conquer algorithms with a big notation of $n log(n)$