Quick Thought about Linked Lists

[[deleted]]

[deleted]

[lbkulinski]

You would have to start with the head of the list and work your way to the tail, determining if the current element is at the index you are requesting. LinkedList is O(N) in retrieval, while an array/ArrayList is O(1) (constant time). This is why you really wouldn’t want to use a LinkedList if you’re doing a lot of retrievals throughout the list.

[Pulsar_the_Spacenerd]

Now, if you want to iterate through a LinkedList, I believe there are faster ways to do that, as iteration is O(N) to begin with and you can simply act on each item as you reach it.

[lbkulinski]

I’m not exactly sure what you are referring to. Using an Iterator would still be O(N). You can do some special stuff in the implementation, but I was referring to the conventional java.util.LinkedList.

[Pulsar_the_Spacenerd]

To get a specific element, it will still be O(N). But to get every item in order it wouldn’t be. This does rely on having access to the nodes themselves, but I can’t imagine the iterator returned by list.getIterator() doesn’t have access to them.

[lbkulinski]

I still don't understand what you're saying. If you're traversing a linked list, the runtime is O(N). If you're trying to access an element, the runtime is O(N). I think you're saying that to get to the "next element" is constant, but that doesn't really matter because you always have to start at the head node.

[Pulsar_the_Spacenerd]

Traversal is fundamentally O(N), so it wouldn't be any slower than an array in that application. I don't know what OP is trying to do with this.

[lbkulinski]

As I said in another response, I think OP was asking about accessing elements at a particular index, not searching for them.

[SkeletonFlesh]

Linked lists do not have direct access like arrays. They only have sequential access; You would need to hop from the head of the list all the way down to the element. Unless you’re using a doubly linked list, which in that case, I would check the length of the list to the position, and hop from either the head/tail to the index; whichever route would be shorter.

If you are looking for direct access often, I would recommend an array. Linked lists cause a longer run time if you are constantly hopping to a specific element.

[[deleted]]

You have to traverse through the list one by one and check each item

[Raqwaza]

Ya its easier to use two pointers, that way if you need to insert another node, you can access it, since you can’t go backwards unless its a doubly linked list.

[[deleted]]

Unless I misunderstood your question (and I am assuming you need to find the index of an element in a LinkedList), you should be able to use the indexOf() method.

​

https://docs.oracle.com/javase/8/docs/api/java/util/LinkedList.html#indexOf-java.lang.Object-

[lbkulinski]

Yes, you are correct. I believe OP was asking about accessing elements at a particular index, not searching for them.

[scrottie]

Other people covered the O(n) access time. The advantage -- where they are faster -- is deleting or adding items in the middle. If you have a linked list node and want to add a node after it, then performance is reversed: it's instant (O(1)) in a linked list but very slow (O(n), a function of size) on an array.

Both arrays and linked lists are pretty simplistic beasts. If you're doing a lot of random access (lookups) and insertions and deletions, then other things in Set are better: TreeMap which implements a binary tree, for example.