0

I don't understand the context in which you'd ever want a linked list over something like an arraylist.

In an arraylist, random access and appends are amortized constant time, inserts and deletes are linear time.

Linked lists, appends and prepends are also constant time (assuming you have pointers to head and tail) as well as inserts and deletes but only once you have the right element -- otherwise things like random access takes linear time.

Why would we ever want the latter? It sounds like inserts and deletes are constant time but only after you spend linear time to find the right element from which to insert or delete.

Is it only preferable if you're doing a lot of appends / deletes from a single spot so it's fast once you find the right one? But then why can't I do the same thing with an arraylist by shifting everything over by k spots and then filling in the inserts? Faster if the remaining size of the array is smaller than the first portion if it had been an arraylist you had to a an through linearly.

Sean Hill
  • 1,297
  • 1
  • 13
  • 21
  • Not a duplicate, I already saw that post / I know the differences in time complexity, I'm asking about usage – Sean Hill Oct 03 '16 at 16:44
  • You'd use `LinkedList` in situations where the different time complexities really matter (and as said in the dupe, that's very rarely). Definitely a duplicate. – Kayaman Oct 03 '16 at 16:46
  • Can you point to where my question is answered ? I genuinely do not see it. I am asking how those different complexities arise and matter in actual context – Sean Hill Oct 03 '16 at 16:50
  • For example if inserts are constant time but search is linear, doesn't that defeat the purpose? You're still bottlenecked by the linear search. – Sean Hill Oct 03 '16 at 16:56
  • Who says you're doing a search? You'd use it for the efficient operations. Not for search, at least if searches are most of your operations. – Kayaman Oct 03 '16 at 16:57
  • But you have to know where to insert before you can insert – Sean Hill Oct 03 '16 at 16:59
  • 1
    One major use case: when your expected number of elements is extremely small, or often zero, so the overhead of an array is more than necessary. This occurs e.g. for hash table buckets, where you expect the overwhelming majority of buckets to have 0 or 1 entry. – Louis Wasserman Oct 03 '16 at 17:00
  • Hash table is then what exactly? An array of linked lists? – Sean Hill Oct 03 '16 at 17:01
  • 3
    What if your use case is removing elements from the beginning of the list? – Marko Topolnik Oct 03 '16 at 17:06
  • See my last paragraph in my post (I also mention that yeah prspending is better in a linked list) – Sean Hill Oct 03 '16 at 17:09
  • It's next to incomprehensible, I can only guess that you imply an O(n) shift of all elements. – Marko Topolnik Oct 03 '16 at 17:10
  • 1
    Prepends in a linked list are constant time. Prepends in an array list are linear time due to shifting of the initial list. But surely linked lists have more uses than merely prepends – Sean Hill Oct 03 '16 at 17:12
  • 1
    If your question is about the general linked list structure and not the specific `LinkedList` implementation, then there are many more uses. For example, all of LISP is based on the `cons` structure, which is a linked list. Linked lists also allow O(1) splicing; there might be some sorting algorithms that specifically target that. – Marko Topolnik Oct 03 '16 at 17:22
  • *"Can you point to where my question is answered"* Yes: 1) "The main benefits of using a LinkedList arise when you re-use existing iterators to insert and remove elements" and 2) "Another benefit of using a LinkedList arise when you add or remove from the head of the list". Right there, smack in the middle of the accepted answer! There is a third reason, that's not listed: LinkedList shrinks, ArrayList doesn't. – Andreas Oct 03 '16 at 17:23
  • Right, really use existing iterators, still linear up front, no? – Sean Hill Oct 03 '16 at 17:25
  • And again when would we actually use this? If we're reusing iterators it may still be less efficient than a full array shift if we're near the end (see my last paragraph in main post) – Sean Hill Oct 03 '16 at 17:27
  • 1
    No, why do you say it's linear up front? You're assuming you know exactly which element(s) to remove, for random access to prevail, but that's not the case here. What if you need to remove all "Male" elements from a `Person` list? You would have to iterate all elements, regardless of list type. The removal operation would then by faster on `LinkedList` (_O(1)_) vs on `ArrayList` (_O(n)_). – Andreas Oct 03 '16 at 17:27
  • Because if you want to insert after some element X you need to find X in the linked list first so you know where to actually do the inserting – Sean Hill Oct 03 '16 at 17:30
  • @Andreas Considering that `LinkedList` is something like 4 times less space-efficient than `ArrayList`, building a new `ArrayList` with filtered elements is probably both more space and more time-efficient. – Marko Topolnik Oct 03 '16 at 17:31
  • Also if I wanted to remove all Male elements from list in linear time I could just make a new list and start inserting non-Males in linear time without a linked list using two pointer technique – Sean Hill Oct 03 '16 at 17:32
  • 1
    That was just an example of *filtered* removal. Maybe it was a bad example, since you're focusing on the 50% hit-rate. What if hit-rate is only 5%? 1%? What is *faster*? Removing 1% or copying 99%? No comparison, *performance-wise*. Those are the cases where LinkedList *performs* better. Extreme case being the remove/insert head. That's why `LinkedList` exist. There are use cases where it's better than `ArrayList`. – Andreas Oct 03 '16 at 17:37
  • That's my question though. What are those use cases (outside of head/tail appends)? – Sean Hill Oct 03 '16 at 18:05
  • For example. Let's say we are inserting k elements at position p for node 0 <= p < n (either we know the index if it's an ArrayList, or we don't know where it is if it's a LinkedList). If it's an ArrayList, this requires (n-p+1) copies of pre-existing array data (the suffix array) and k inserts for a total of n-p+k+1 operations. For a LinkedList, this requires p scans (to find the element) and then k insert operations for a total of p+k operations. n-p+k+1 < p+k when roughly n/2 <= p, meaning ArrayList inserting is better if you're doing it past the halfway point of the list. – Sean Hill Oct 03 '16 at 18:13
  • If we don't know where p is, then its expected position assuming uniform random distribution is n/2 itself, so it means for insertions, half the time ArrayList will be better, and half the time LinkedList will be better. – Sean Hill Oct 03 '16 at 18:14

0 Answers0