CODEWITHSUNDEEP
stringdata-structures
JoeG
JoeG

Reputation: 13192

Data structure for storing strings?

I'm looking for a data structure to store strings in. I require a function in the interface that takes a string as its only parameter and returns a reference/iterator/pointer/handle that can be used to retrieve the string for the rest of the lifetime of the data structure. Set membership, entry deletion etc. is not required.

I'm more concerned with memory usage than speed.

Upvotes: 4

Views: 21002

Answers (4)

sangita bora
sangita bora

Reputation: 1

There are three ways to store strings:

  1. Fixed length (array type structure)
  2. Variable length but maximum size is fixed during running time (pointer type structure)
  3. Linked list structure

Upvotes: 0

Avi
Avi

Reputation: 20142

One highly efficient data structure for storing strings is the Trie. This saves both memory and time by storing strings with common prefixes using the same memory.

alt text

You could use as the pointer returned the final marker of the string in the Trie, which uniquely identifies the string, and could be used to recreate the string by traversing the Trie upwards.

Upvotes: 16

Zach Scrivena
Zach Scrivena

Reputation: 29539

I think the keyword here is string interning, where you store only one copy of each distinct string. In Java, this is accomplished by String.intern():

String ref1 = "hello world".intern();
String ref2 = "HELLO WORLD".toLowerCase().intern();
assert ref1 == ref2;

Upvotes: 3

Gonzalo Quero
Gonzalo Quero

Reputation: 3323

I think the best bet here would be an ArrayList. The common implementations have some overhead from allocating extra space in the array for new elements, but if memory is such a requirement, you can allocate manually for each new element. It will be slower, but will only use the necessary memory for the string.

Upvotes: 0

Related Questions