Questions tagged [data-structures]
Questions regarding efficient storage and representation of data within a software application.
901
questions
18
votes
4
answers
23k
views
What are concrete rules for using a linked list instead of an array?
A linked list can be used when you want cheap insertion and deletion of elements and when it doesn't matter that the elements aren't next to each other in memory.
This is very abstract and I would ...
user4595
18
votes
9
answers
5k
views
How is polymorphism used in the real world? [closed]
I am trying to understand how Polymorphism is used in a real life project, but I can only find the classical example (or something similar to it) of having an Animal parent class with a methodspeak(), ...
- 2,039
18
votes
1
answer
4k
views
How does a skip list work?
For a homework assignment, I need to understand how a skip list works.
I've been programming for a little over 2 years now (I know that's not that long in reality), and I have never even heard of a ...
- 2,653
18
votes
8
answers
20k
views
What's the difference between a stream and a queue?
What's the difference between a stream and a queue? They both have the concept of an ordered set of elements, but tend to have different implementations and a different vocabulary of 'insert'/'...
- 871
18
votes
11
answers
14k
views
What is the most complicated data structure you have used in a practical situation? [closed]
The germ for this question came up from a discussion I was having with couple of fellow developers from the industry.
Turns out that in a lot of places project managers are wary about complex data ...
- 7,493
17
votes
8
answers
15k
views
Is having trouble with data structures common for beginners? [closed]
I'm taking my second course on Java. We are getting into data structures. I have done an assignment on a linked list, and now a stack. I had a hard time with the linked list. The stack gave me a ...
- 187
17
votes
6
answers
51k
views
Is it wise to store a big lump of json on a database row
I have this project which stores product details from amazon into the database.
Just to give you an idea on how big it is:
[
{
"title": "Genetic Engineering (Opposing Viewpoints)&...
- 857
17
votes
7
answers
6k
views
How far to go with typedef'ing primitive types like int
I have seen C++ code such as the following with many typedefs.
What are the benefits of using many typedefs like this as opposed to using C++ primitives? Is there another approach that might also ...
- 273
17
votes
2
answers
10k
views
Are bloom filters actually faster than hashes, even taking in account cache?
Bloom filters look really great when you consider you can determine if an Int is in a set with 99% certainty in constant time. But so can hashes, with the only difference that, in a hash, most of the ...
- 5,830
17
votes
2
answers
1k
views
What is the canonical reference on probabilistic data structures?
I've heard of probabilistic data structures like Skip Lists and Bloom Filters being immensely useful and I'd like to learn more about them in general. Is there a canonical reference on the subject on ...
user28988
16
votes
4
answers
30k
views
Is storing a list of strings in single database field a bad idea? Why?
Recently, I started to work on some legacy system. People that developed it, came to an idea to store list of strings in single field of database table. Lets say that it is an identifier for object ...
- 336
16
votes
4
answers
3k
views
Uses of persistent data structures in non-functional languages
Languages that are purely functional or near-purely functional benefit from persistent data structures because they are immutable and fit well with the stateless style of functional programming.
But ...
- 1,315
16
votes
2
answers
8k
views
How should I design an ordered list resource in a restful service?
I've run into this same problem over and over again and I haven't found a solution that I really felt was optimal.
Say in an app, you have an ordered list and you let the user change that order by ...
- 240
16
votes
3
answers
6k
views
How do scalable bloom filters work?
I was reading up on scalable bloom filters and could not understand how each time a constituent bloom filters fills up, a new bloom filter with larger size is added.
The elements that contributed to ...
- 279
16
votes
4
answers
2k
views
What did Bill Gosper mean by saying a data structure is just a stupid programming language? [closed]
There's a quotation by Ralph William Gosper, Jr that says:
A data structure is just a stupid programming language.
What did he mean by this? Alas, all I can find in Google about it is relentless ...
- 3,886
16
votes
5
answers
10k
views
Understanding Abstract Data Types (ADTs) [duplicate]
Just browsing through Code Complete last night and I came across the explanation of abstract data types.
I must have read it 5 times, and the Wikipedia article doesn't help much either. So what I'm ...
- 6,549
15
votes
4
answers
11k
views
Can a C struct behave like it had a function?
I use C and structs where a struct can have members but not functions. Assume for simplicity that I want to create a struct for strings that I name str and I want to be able to do str.replace(int i, ...
- 8,068
15
votes
4
answers
7k
views
Is there a standard way or standard alternative to packing a struct in c?
When programming in C I have found it invaluable to pack structs using GCCs __attribute__((__packed__)) attribute so I can easily convert a structured chunk of volatile memory to an array of bytes to ...
- 730
15
votes
5
answers
2k
views
Storing in-text metadata in a discrete data structure
I am developing an application which will need to store inline, intext metadata. What I mean by that is the following: let's say we have a long text, and we want to store some metadata connected with ...
- 440
14
votes
5
answers
7k
views
Is there a specific purpose for heterogeneous lists?
Coming from a C# and Java background, I'm used to my lists being homogeneous, and that makes sense to me. When I started picking up Lisp, I noticed that the lists can be heterogeneous. When I started ...
- 5,163
14
votes
3
answers
14k
views
AVL Trees and the REAL world
in school we are taught how we can balance an AVL tree upon an insertion or deleting.
How is this type of knowledge actually going to be useful in the real world?
Can someone give an example on when ...
- 1,398
14
votes
8
answers
28k
views
Practical way to store a "reasonably large" amount of data that hardly ever changes?
Think in terms of pre-computed lookup tables or something. At what point does it make more sense to use a database instead of hardcoding values in my application? The values are not going to change, ...
- 2,774
14
votes
2
answers
12k
views
Why does Python use hash table to implement dict, but not Red-Black Tree? [closed]
Why does Python use hash table to implement dict, but not Red-Black Tree?
What is the key? Performance?
- 253
14
votes
2
answers
9k
views
What is the most space efficient way to implement a graph data structure?
I typically implement graphs as doubly linked lists but this is fairly space inefficient in my experience as I need k pointers/references for k neighbors so for an undirected graph I'd have ~2k ...
user28988
14
votes
2
answers
6k
views
Amortized Analysis? (Worst-case Performance Guarantees)
What is Amortized Analysis? And how can it help me achieve worst-case performance guarantees in my programs?
I was reading that the following techniques can help the programmer achieve Worst-case ...
- 900
13
votes
8
answers
51k
views
What is the difference between an Array and a Stack?
According to Wikipedia, a stack:
is a last in, first out (LIFO) abstract data type and linear data structure.
While an array:
is a data structure consisting of a collection of elements (values ...
- 5,746
13
votes
2
answers
3k
views
Is there a common term for a fixed-length, fifo, "push through" array or list?
Here's a ubiquitous data structure in, say, game and UX programming:
there're a fixed number of items (say, "5")
they're all "zero" to begin with
you can put one in on the "...
- 437
13
votes
3
answers
7k
views
Why do Haskell and Scheme use singly-linked lists?
A doubly linked list has minimal overhead (just another pointer per cell), and allows you to append to both ends and go back and forth and generally have a lot of fun.
13
votes
7
answers
20k
views
How important is studying algorithms and theory is to becoming a great programmer? [duplicate]
Possible Duplicate:
Should I keep investing into data structures and algorithms?
I'm a CS student. I want to become a really great programmer, what do I need to do to be come a great programmer? ...
- 349
13
votes
2
answers
14k
views
What is the relationship between data structures and algorithms? [closed]
I have been searching for a good online course in data structures but have found that Google also returns results for algorithms courses, which say stuff like:
In this course you will learn several ...
- 1,102
13
votes
2
answers
13k
views
Is it possible to speed up a hash table by using binary search trees for separate chaining?
I want to implement a Hash Table using Binary Search Trees to reduce the search complexity in the Separate Chaining process from O(n) (using linked list) to O(log n) (using BST). Can this be done, and ...
- 149
13
votes
4
answers
48k
views
Nested maps vs. combined keys
in the project I am currently working on we had three different types of prices depending on the age of the user (adult, child, etc...). So we had on the DB a table looking like this:
PRICES
type ...
- 309
13
votes
2
answers
5k
views
Is a tree with nodes that have reference to parent still a tree?
If we make reference to the parent for each node in a tree, do we still have a tree (by definition) anymore?
Wikipedia definition is:
In computer science, a tree is a widely used abstract data ...
- 1,990
13
votes
5
answers
7k
views
Data structures in functional programming
I'm currently playing with LISP (particularly Scheme and Clojure) and I'm wondering how typical data structures are dealt with in functional programming languages.
For example, let's say I would like ...
- 655
13
votes
5
answers
10k
views
What data structure should I use for this caching strategy?
I am working on a .NET 4.0 application, that performs a rather expensive calculation on two doubles returning a double. This calculation is performed for each one of several thousand items. These ...
- 3,019
13
votes
3
answers
20k
views
What is the underlying mechanism behind va_list and where is it defined?
http://www.cplusplus.com/reference/cstdarg/va_list/
According to the above link, va_list is an argument or parameter used in some macros - va_start, va_arg, va_end. These macros are present in the ...
- 419
13
votes
3
answers
4k
views
What is the Bible of Hashing?
Is there a Cormen-like reference on Hashes and Hashing? This particular structure has seen little attention in my CS education for some reason but I'd like to learn more as they seem to be everywhere. ...
user28988
12
votes
3
answers
839
views
Do binary trees serve a specific purpose in storing hierarchical data? What is their canonical use?
I understand the structure of binary trees and how to traverse them. However, I am struggling to realize their actual uses, purposes in programs and programming. When I think about 'real life' ...
- 249
12
votes
5
answers
3k
views
Quadtree with duplicates
I'm implementing a quadtree. For those who don't know this data structure, I am including the following small description:
A Quadtree is a data structure and is in the Euclidean plane
what an ...
- 1,339
12
votes
2
answers
10k
views
Using a stream manipulator (endl) or a newline escape character (\n)?
I don't have a specific context in which I'm asking the question, but while I was reading a beginner book on C++ I noticed the use of both an endl stream manipulator and a newline escape character ...
- 123
12
votes
4
answers
6k
views
Are trees organised by a "firstchild, nextsibling" structure? If not, why not?
Usually, tree data structures are organised in a way that each node contains pointers to all its children.
+-----------------------------------------+
| root ...
- 28.4k
12
votes
2
answers
1k
views
Workaround for implementing operations on doubly linked or circular data structures in languages with immutable data
I would like to learn how to make graphs and perform some local operations on them in Haskell, but the question is not specific to Haskell, and instead of graphs we may consider doubly linked lists.
...
- 932
12
votes
2
answers
3k
views
Pseudocode for Brodal queue
I'm trying to find more resources regarding Brodal heap. All I found is a haskell implementation of Brodal-Okasaki heap, but I think that they are skew heaps, is this correct? Furthermore, I'm ...
- 391
12
votes
2
answers
1k
views
Data structure for multi key range queries
I need a data structure that gives the best performance for multi-key range lookups. I do not need to update/insert/delete. This will be immutable. The use case is in-memory filtering of values over ...
- 267
12
votes
1
answer
5k
views
What do banks actually use as a data type for money? [closed]
I'm aware of a few good options:
Big integers (e.g., int64_t, mpz_t, any bignum lib) to represent cents or 10-n cents—say, an integer represents 1/100 of a penny ($1.05 == 10500). This is called a ...
- 565
11
votes
6
answers
18k
views
What do you call classes without methods?
What do you call classes without methods?
For example,
class A
{
public string something;
public int a;
}
Above is a class without any methods. Does this type of class have a special name?
- 221
11
votes
4
answers
6k
views
What are the differences between algorithms using data structures and algorithms using databases?
The General Question
What are the differences between algorithms using data structures and algorithms using databases?
Some Context
This is a question that has been bugging me for some time, and I ...
11
votes
3
answers
21k
views
Should Linked Lists always have a tail pointer?
My understanding...
Advantages:
Inserting at the end is O(1) instead of O(N).
If the list is a Doubly Linked List, then removing from the end is also O(1) instead of O(N).
Disadvantage:
Takes up a ...
- 615
11
votes
4
answers
767
views
Good code style to introduce data checks everywhere?
I have a project that is sufficiently large in size that I can't keep every aspect in my head any more. I'm dealing with a number of classes and functions in it, and I'm passing data around.
With ...
- 569
11
votes
4
answers
501
views
Why is it that MS Data Access story is so fractured ? Is it the nature of Data Access or is just MS?
This StackOverflow question asks "where can I get Microsoft.Data.Objects"
It turns out the answer was probably that its in the CTP4 (code first) release of Entity Framework 4
However there where a ...
- 4,155