posted 3 months ago

Well, one iterates over the nodes until it hits the specified index, and the other iterates over the nodes until it hits the specified element. Regardless, they both have to iterate a chain of nodes once.

*The mind is a strange and wonderful thing. I'm not sure that it will ever be able to figure itself out, everything else, maybe. From the atom to the universe, everything, except itself.*

Lilou Laure

Ranch Hand

Posts: 96

10

posted 3 months ago

so the time complexity will be O(n) except when we refer to the first or last elements, for which it'll be O(1).

Similarly in doubly linked lists too, when either of the remove methods are used, it'll be the same as above right ? because even though finding the successor and predecessor will be O(1), to iterate to the desired element it may take O(n) . Is this right ?

Similarly in doubly linked lists too, when either of the remove methods are used, it'll be the same as above right ? because even though finding the successor and predecessor will be O(1), to iterate to the desired element it may take O(n) . Is this right ?

posted 3 months ago

Don't try to reduce complexity to fit in such corner cases. Even in the case of extreme values, the complexity remainsLilou Laure wrote:. . . when we refer to the first or last elements, for which it'll be O(1).

*(*

**O***n*), even though

*n*= 1. That does not reduce to constant time.

Yes; the time taken on average to remove something from a linked list remains linear time; there is no such thing asSimilarly in doubly linked lists too, when either of the remove methods are used, it'll be the same as above right . . . to iterate to the desired element it may take O(n) . Is this right?

*(*

**O***n ÷ 2*) complexity.

Lilou Laure

Ranch Hand

Posts: 96

10

Stephan van Hulst

Saloon Keeper

Posts: 7994

143

posted 3 months ago

Complexity classes are not concerned with specific cases, they're only used to indicate how fast a function grows.

You can say "Getting an element at a

Even though this method gets an element that's possibly in the middle of a linked list (if the list has close to a 100 elements), it still operates in

Note that it's important to specify what

Lilou Laure wrote:so the time complexity will be O(n) except when we refer to the first or last elements, for which it'll be O(1).

Complexity classes are not concerned with specific cases, they're only used to indicate how fast a function grows.

You can say "Getting an element at a

**fixed**index in a linked list of size

`n`performs in

`O(1)`", or you can say "Getting an element at a

**given**index om a linked list of size

`n`performs in

`O(n)`", but these are different operations. It doesn't matter what the exact value of n is. Here's an example of an

`O(1)`operation:

Even though this method gets an element that's possibly in the middle of a linked list (if the list has close to a 100 elements), it still operates in

`O(1)`, because the amount of time it takes does not depend on the size of the list. It will take equally long for a list of a thousand elements.

Note that it's important to specify what

`n`stands for. In your first method,

`n`was taken to be the shortest distance between the index and the start or end of the list. In your second method,

`n`was taken to be the size of the list. If instead, for the method r

`emove(int index)`,

`d`stands for the shortest distance between the start and end of the list, and

`n`stands for the size of the list, then the operation performs in

`O(d)`, not

`O(n)`.

Campbell Ritchie

Marshal

Posts: 56610

172

posted 3 months ago

That is a good question; have a look at the documentation for it.

The first stage of removal runs in constant time because it is possible to find each element from its index with the underlying array; moving the remaining elements in the array to occupy that space however takes a time dependent on the size of the List.All of the other operations run in linear time (roughly speaking).

Did you see how Paul cut 87% off of his electric heat bill with 82 watts of micro heaters? |