算法November 27, 2018 at 08:00 PM作者单一鸣4 分钟阅读2 个标签

Data Structure 2 - Quick Comparison

Data Structures — A Quick Comparison (Part 2)

Data Structures — A Quick Comparison (Part 2) Data Structures 2-Quick Comparison

Comparison between different data structures — bigochheatsheet.com Comparison between different data structures - bigochheatsheet.com

Each data structure has it’s own different way, or different algorithm for sorting, inserting, finding, …etc. This is due to the nature of the data structure. There are algorithms used with specific data structure, where some other can’t be used. Each data structure has its own different methods or algorithms for sorting, inserting, searching, etc. This is due to the nature of the data structure. Some algorithms have specific data structures that other algorithms cannot use.

The more efficient & suitable the algorithm, the more you will have an optimized data structure. The more efficient and appropriate the algorithm is, the more optimized data structures will be obtained.

Chances are, you’re going to rely on the built-in algorithms used with the data structures in your language. These algorithms are very well optimized and battle tested. Most likely, you will rely on built-in algorithms that work with data structures in your language. These algorithms are well optimized and tested.

arrays array

pros Advantages

Easy to create, Easy to use Easy to create, easy to use
Direct indexing: O(1) Direct indexing: O(1)
Sequential access: O(N) Sequential access: O(N)

cons Disadvantages

Sorting: O(NLogN) Sorting: O(NLogN)
Searching: O(N), and O(LogN) if sorted Searching: O(N) and O(LogN) if sorted
Inserting and deleting: O(N) because of shifting items.

linked list linked list

pros Advantages

Inserting and deleting: O(1). Inserting and deleting: O(1)
Sequential Access: O(N) Sequential Access: O(N)

Inserting and deleting operations refers to the operation itself, as you might need to sequentially access all the nodes until the node you’are looking for.

Inserting and deleting is much easier with doubly linked list.

cons Disadvantages

No Direct Access; Only Sequential Access. No direct access; Only sequential access.
Searching: O(N) Searching: O(N)
Sorting: O(NLogN) Sorting: O(NLogN)

Stacks and Queues Stacks and Queues

Stacks and queues have very specific purposes. Stacks are last in, first out data structure (LIFO), while queues are first in, first out (FIFO). Stacks and queues serve very specific purposes. The stack is a last-in-first-out data structure (LIFO), while the queue is a first-in, first-out (FIFO) data structure.

pros Advantages

Push/Add: O(1)
Pop/Remove: O(1)
Peek: O(1)

Cons

If you’re trying to do anything else with stacks or queues, like if you’re asking how can I pull an item from the middle?. Then, you should be looking at a different data structure. If you want to do anything else with a stack or queue, like if you want to know how to extract an item from the middle? Then you should look at the different data structures.

Hash Tables. Hash table

pros Advantages

Inserting and deleting: O(1) + Hashing & Indexing (amortized). Inserting and deleting: O(1) + Hashing & Indexing (amortized).
Direct access: O(1) + Hashing & Indexing. Direct access: O(1) + Hashing & Indexing.

It takes a little processing for the hashing and indexing. But the good thing about that is it’s the same amount of processing every time, even if the hash table gets very large. Hashing and indexing take some processing. But the advantage of this is that the number processed each time is the same, even if the hash table becomes very large.

When the hash table gets full, it will increase it’s size. And, when the number of filled buckets is much smaller than the size of the hash table, it will then decrease it’s size. Both operations take a complexity of O(N). That’s why insertion and deletion takes O(1) amortized. When the hash table fills up, it increases its size. When the number of filled buckets is much smaller than the size of the hash table, it reduces its size. The complexity of both operations is O(N). This is why insertion and deletion require O(1) amortization.

cons Disadvantages

Some overhead as require a little more space in memory than arrays. Some overhead as require a little more space in memory than arrays.
Retrieval of elements doesn’t guarantee a specific order. Retrieval of elements doesn’t guarantee a specific order.
Searching for a value (without knowing it’s key). Searching for a value (without knowing it’s key).

sets sets

pros. Advantages

Checking membership; value existence. Checking membership; value existence.
Avoids duplicates avoid duplication

The complexity of checking if a value contained in the set depends on the underlying data structure used to implement the set.

In C++, It uses a binary search tree (probably a red black tree; a type of self balancing binary search tree). So, the complexity would be O(LogN), and O(N) if the tree is unbalanced. The complexity is O(LogN) if the tree is unbalanced, the complexity is O(N)

In Java, HashSet class implements the Set Interface using the hash table data structure. So, the complexity would be the same as the hash tables (see above). In Java, the HashSet class implements the Set interface using a hash table data structure. Therefore the complexity will be the same as a hash table (see above).

Cons

Sets are intentionally limited. There aren’t much you can do with them. So, they’re terrible at almost everything else. Collections are intentionally limited. There’s nothing you can do about them. So, they’re terrible in almost every other way.### Binary Search Trees (BST)