1

Could I make a list with everything having fast running time? Is it possible having this type of list? I can't wrap my head around how you could keep search or add times being constant if it needs to go through nodes to search for others, much less adding.

Saadin Dassum
  • 19
  • 5
  • 1
    What do you mean by "that beats the purpose of having a list"? – Glen Pierce May 02 '17 at 01:38
  • If you used an expanding list that doubles in size as you need it, you could achieve amortized O(1) getting, setting, and adding, which just means you'd eventually need to expand its size, but that doesn't happen often enough. Pretty sure this is how Java's ArrayList class works. – iptq May 02 '17 at 01:38
  • "I can't wrap my head around how you could keep search or add times at o(1)" Also, search time would NOT be O(1). Only get, set, and add. – iptq May 02 '17 at 01:41
  • *I can't wrap my head around how you could keep search or add times at o(1)*. Who said anything about search times? – shmosel May 02 '17 at 01:42
  • @failed.down Talking to me? I read the question... obviously. My question was directed to OP. – shmosel May 02 '17 at 01:47
  • @shmosel I believe OP is just misusing the word `searching` to mean `get()` or `indexed-access` – Adrian Shum May 02 '17 at 02:22
  • @AdrianShum I suspect the same. It's led to a lot of pointless discussion in the answers and comments. – shmosel May 02 '17 at 02:26
  • 1
    Just want to clarify: is `add()` here means only `add(E element)` (adding to the end of list, or also `add(int index, E element)` (adding to a specific index)? If it includes the latter case, then I don't think there is any solution (yet). If you only need former case, then `ArrayList` is already serving your purpose (explained in other answer) – Adrian Shum May 02 '17 at 02:37
  • @Glen Pierce what I mean by that is that I feel the point of a list is searching by links. If you're going to search by hashing, is that really a list? – Saadin Dassum May 02 '17 at 14:10
  • @Kaz "with references to the order and to pointers, but that beats the purpose of having a list"... I'm confused as to why you think I don't think that means he intends to " maintain a sequence of elements, in which successors and predecessor relationships are clearly identified and maintained". You're being remarkably rude for someone with a public profile. – Glen Pierce May 02 '17 at 14:51

2 Answers2

1

At first you only said get(), add() and set(), but then you said search() as well. The first three all have O(1) average run time in an ArrayList and similar implementations. You can't have O(1) search time in anything that would normally be considered a list.

Edit: Some people have pointed out, correctly, that you could get O(1) lookup time if the list implementation also stored element indices in a hashmap. Strictly speaking, as long as it implements a List interface, it is a list. I should have said that you can't do that with only a list.

John Angland
  • 446
  • 3
  • 12
  • 2
    Unless the list was indexed with a hash table. – selbie May 02 '17 at 01:46
  • @selbie Then it wouldn't be a list. – shmosel May 02 '17 at 01:56
  • @shmosel You could extend `ArrayList` and override `indexOf` to be backed by a `HashMap`, unless does using a hash table in the implementation automatically make it not a list? – 4castle May 02 '17 at 02:07
  • 1
    @4castle That's actually a neat idea. My point is that an array list and hash table are separate data structures. Sure, they can share a roof to reduce time complexity (at an increased memory and write cost), so maybe it's a "`java.util.List` with O(1) search time", but I wouldn't call it a "list [structure] with O(1) search time". – shmosel May 02 '17 at 02:14
  • But what about when you run out of space and have to rehash? That takes O(n) times (n being the number of elements you have) – Saadin Dassum May 03 '17 at 19:16
  • Expanding the inner array in a hashmap takes O(n), but only occurs O(1/n) of the time, so insertion is still O(1). – John Angland May 03 '17 at 23:42
0

Just posting my comment as an answer...

If you used an expanding list that expands in size as you need it, you could achieve amortized O(1) getting, setting, and adding, which just means you'd eventually need to expand its size, but that doesn't happen often enough. Pretty sure this is how Java's ArrayList class works.

You can read more about it here. https://stackoverflow.com/a/4450659/1572906

You mentioned searching, but with this kind of approach, O(1) doesn't seem very feasible. You could achieve O(1) using a hash table alongside the array.

Community
  • 1
  • 1
iptq
  • 657
  • 1
  • 7
  • 15
  • 1
    Hash tables are generally considered to be O(1) in the amortized/average case. So search could be O(1) ... – selbie May 02 '17 at 01:53
  • 1
    HashSet `put()` and `get()` are both _O(1)_. TreeSet is _O(log n)_ – Andreas May 02 '17 at 01:53
  • `add()` in `ArrayList` may be `O(n)`, as there is an `add(int index, E element)`. It is `O(1)` only if you only consider adding at the end of list. I believe OP should be clearer on his question – Adrian Shum May 02 '17 at 02:26
  • my bad, you're right. i fixed it; idk what i was thinking – iptq May 02 '17 at 04:51