Does Java's internal LinkedList implementation traverse starting from the head or tail appropriately...

Multi tool use
.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty{ height:90px;width:728px;box-sizing:border-box;
}
This question already has an answer here:
Is Java's LinkedList optimized to do get(index) in reverse when necessary?
1 answer
Since Java implementation of the LinkedList is a doubly linked list. Would it not make more sense if say an index passed to the get get(int index) method was past the middle of the linkedlist, That the value was obtained using the descending iterator from the tail of the list?
Does this happen?
If it does not why?
Example say I have a linkedList like below:
head tail
A <-> B <-> C <-> D <-> E <-> F <-> G
And I said linkedList.get(5) to get the second the last element in the linkedList. Would java use the decending iterator (start from the tail) internally to retrive F, or not? Since 5 is past the middle of the linkedlist.
java linked-list doubly-linked-list
marked as duplicate by PM 77-1, shash678, Mark Rotteveel
StackExchange.ready(function() {
if (StackExchange.options.isMobile) return;
$('.dupe-hammer-message-hover:not(.hover-bound)').each(function() {
var $hover = $(this).addClass('hover-bound'),
$msg = $hover.siblings('.dupe-hammer-message');
$hover.hover(
function() {
$hover.showInfoMessage('', {
messageElement: $msg.clone().show(),
transient: false,
position: { my: 'bottom left', at: 'top center', offsetTop: -7 },
dismissable: false,
relativeToBody: true
});
},
function() {
StackExchange.helpers.removeMessages();
}
);
});
});
Jan 4 at 12:50
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
add a comment |
This question already has an answer here:
Is Java's LinkedList optimized to do get(index) in reverse when necessary?
1 answer
Since Java implementation of the LinkedList is a doubly linked list. Would it not make more sense if say an index passed to the get get(int index) method was past the middle of the linkedlist, That the value was obtained using the descending iterator from the tail of the list?
Does this happen?
If it does not why?
Example say I have a linkedList like below:
head tail
A <-> B <-> C <-> D <-> E <-> F <-> G
And I said linkedList.get(5) to get the second the last element in the linkedList. Would java use the decending iterator (start from the tail) internally to retrive F, or not? Since 5 is past the middle of the linkedlist.
java linked-list doubly-linked-list
marked as duplicate by PM 77-1, shash678, Mark Rotteveel
StackExchange.ready(function() {
if (StackExchange.options.isMobile) return;
$('.dupe-hammer-message-hover:not(.hover-bound)').each(function() {
var $hover = $(this).addClass('hover-bound'),
$msg = $hover.siblings('.dupe-hammer-message');
$hover.hover(
function() {
$hover.showInfoMessage('', {
messageElement: $msg.clone().show(),
transient: false,
position: { my: 'bottom left', at: 'top center', offsetTop: -7 },
dismissable: false,
relativeToBody: true
});
},
function() {
StackExchange.helpers.removeMessages();
}
);
});
});
Jan 4 at 12:50
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
2
Wouldn't it be fun and easier to just fire up the debugger and verify the behavior?
– Scorpion
Jan 3 at 22:15
Java (as you probably know) is open source. Nothing stops you from finding out.
– PM 77-1
Jan 3 at 22:20
add a comment |
This question already has an answer here:
Is Java's LinkedList optimized to do get(index) in reverse when necessary?
1 answer
Since Java implementation of the LinkedList is a doubly linked list. Would it not make more sense if say an index passed to the get get(int index) method was past the middle of the linkedlist, That the value was obtained using the descending iterator from the tail of the list?
Does this happen?
If it does not why?
Example say I have a linkedList like below:
head tail
A <-> B <-> C <-> D <-> E <-> F <-> G
And I said linkedList.get(5) to get the second the last element in the linkedList. Would java use the decending iterator (start from the tail) internally to retrive F, or not? Since 5 is past the middle of the linkedlist.
java linked-list doubly-linked-list
This question already has an answer here:
Is Java's LinkedList optimized to do get(index) in reverse when necessary?
1 answer
Since Java implementation of the LinkedList is a doubly linked list. Would it not make more sense if say an index passed to the get get(int index) method was past the middle of the linkedlist, That the value was obtained using the descending iterator from the tail of the list?
Does this happen?
If it does not why?
Example say I have a linkedList like below:
head tail
A <-> B <-> C <-> D <-> E <-> F <-> G
And I said linkedList.get(5) to get the second the last element in the linkedList. Would java use the decending iterator (start from the tail) internally to retrive F, or not? Since 5 is past the middle of the linkedlist.
This question already has an answer here:
Is Java's LinkedList optimized to do get(index) in reverse when necessary?
1 answer
java linked-list doubly-linked-list
java linked-list doubly-linked-list
asked Jan 3 at 22:13


Vipul ChauhanVipul Chauhan
383
383
marked as duplicate by PM 77-1, shash678, Mark Rotteveel
StackExchange.ready(function() {
if (StackExchange.options.isMobile) return;
$('.dupe-hammer-message-hover:not(.hover-bound)').each(function() {
var $hover = $(this).addClass('hover-bound'),
$msg = $hover.siblings('.dupe-hammer-message');
$hover.hover(
function() {
$hover.showInfoMessage('', {
messageElement: $msg.clone().show(),
transient: false,
position: { my: 'bottom left', at: 'top center', offsetTop: -7 },
dismissable: false,
relativeToBody: true
});
},
function() {
StackExchange.helpers.removeMessages();
}
);
});
});
Jan 4 at 12:50
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
marked as duplicate by PM 77-1, shash678, Mark Rotteveel
StackExchange.ready(function() {
if (StackExchange.options.isMobile) return;
$('.dupe-hammer-message-hover:not(.hover-bound)').each(function() {
var $hover = $(this).addClass('hover-bound'),
$msg = $hover.siblings('.dupe-hammer-message');
$hover.hover(
function() {
$hover.showInfoMessage('', {
messageElement: $msg.clone().show(),
transient: false,
position: { my: 'bottom left', at: 'top center', offsetTop: -7 },
dismissable: false,
relativeToBody: true
});
},
function() {
StackExchange.helpers.removeMessages();
}
);
});
});
Jan 4 at 12:50
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
2
Wouldn't it be fun and easier to just fire up the debugger and verify the behavior?
– Scorpion
Jan 3 at 22:15
Java (as you probably know) is open source. Nothing stops you from finding out.
– PM 77-1
Jan 3 at 22:20
add a comment |
2
Wouldn't it be fun and easier to just fire up the debugger and verify the behavior?
– Scorpion
Jan 3 at 22:15
Java (as you probably know) is open source. Nothing stops you from finding out.
– PM 77-1
Jan 3 at 22:20
2
2
Wouldn't it be fun and easier to just fire up the debugger and verify the behavior?
– Scorpion
Jan 3 at 22:15
Wouldn't it be fun and easier to just fire up the debugger and verify the behavior?
– Scorpion
Jan 3 at 22:15
Java (as you probably know) is open source. Nothing stops you from finding out.
– PM 77-1
Jan 3 at 22:20
Java (as you probably know) is open source. Nothing stops you from finding out.
– PM 77-1
Jan 3 at 22:20
add a comment |
2 Answers
2
active
oldest
votes
It would be more fun and perhaps easier to fire up the debugger and verify the behavior. Alternatively, refer to the documentation of Linked List, in particular
All of the operations perform as could be expected for a
doubly-linked list. Operations that index into the list will
traverse the list from the beginning or the end, whichever is
closer to the specified index.
Thanks I wanted to get the second to last element, and I thought using get(list.size() - 1) might be really slow if it was traversing from the start.
– Vipul Chauhan
Jan 3 at 22:20
I frist tried to use getLast().prev() but there was no method :)
– Vipul Chauhan
Jan 3 at 22:21
I am coding on leetcode.com on a ipad which does not have acess to source code completion or a local java installation.
– Vipul Chauhan
Jan 3 at 22:22
2
@VipulChauhan The second to last element would belist.get(list.size() - 2)
– shash678
Jan 3 at 22:38
add a comment |
Looking at the source code answers the question pretty quickly (the answer is yes):
/**
* Returns the element at the specified position in this list.
*
* @param index index of the element to return
* @return the element at the specified position in this list
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
/**
* Returns the (non-null) Node at the specified element index.
*/
Node<E> node(int index) {
// assert isElementIndex(index);
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
Thanks I was coding on a platform that had no code completion/jump to def, (leetcode on an ipad).
– Vipul Chauhan
Jan 3 at 22:26
add a comment |
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
It would be more fun and perhaps easier to fire up the debugger and verify the behavior. Alternatively, refer to the documentation of Linked List, in particular
All of the operations perform as could be expected for a
doubly-linked list. Operations that index into the list will
traverse the list from the beginning or the end, whichever is
closer to the specified index.
Thanks I wanted to get the second to last element, and I thought using get(list.size() - 1) might be really slow if it was traversing from the start.
– Vipul Chauhan
Jan 3 at 22:20
I frist tried to use getLast().prev() but there was no method :)
– Vipul Chauhan
Jan 3 at 22:21
I am coding on leetcode.com on a ipad which does not have acess to source code completion or a local java installation.
– Vipul Chauhan
Jan 3 at 22:22
2
@VipulChauhan The second to last element would belist.get(list.size() - 2)
– shash678
Jan 3 at 22:38
add a comment |
It would be more fun and perhaps easier to fire up the debugger and verify the behavior. Alternatively, refer to the documentation of Linked List, in particular
All of the operations perform as could be expected for a
doubly-linked list. Operations that index into the list will
traverse the list from the beginning or the end, whichever is
closer to the specified index.
Thanks I wanted to get the second to last element, and I thought using get(list.size() - 1) might be really slow if it was traversing from the start.
– Vipul Chauhan
Jan 3 at 22:20
I frist tried to use getLast().prev() but there was no method :)
– Vipul Chauhan
Jan 3 at 22:21
I am coding on leetcode.com on a ipad which does not have acess to source code completion or a local java installation.
– Vipul Chauhan
Jan 3 at 22:22
2
@VipulChauhan The second to last element would belist.get(list.size() - 2)
– shash678
Jan 3 at 22:38
add a comment |
It would be more fun and perhaps easier to fire up the debugger and verify the behavior. Alternatively, refer to the documentation of Linked List, in particular
All of the operations perform as could be expected for a
doubly-linked list. Operations that index into the list will
traverse the list from the beginning or the end, whichever is
closer to the specified index.
It would be more fun and perhaps easier to fire up the debugger and verify the behavior. Alternatively, refer to the documentation of Linked List, in particular
All of the operations perform as could be expected for a
doubly-linked list. Operations that index into the list will
traverse the list from the beginning or the end, whichever is
closer to the specified index.
answered Jan 3 at 22:17
ScorpionScorpion
3,6521936
3,6521936
Thanks I wanted to get the second to last element, and I thought using get(list.size() - 1) might be really slow if it was traversing from the start.
– Vipul Chauhan
Jan 3 at 22:20
I frist tried to use getLast().prev() but there was no method :)
– Vipul Chauhan
Jan 3 at 22:21
I am coding on leetcode.com on a ipad which does not have acess to source code completion or a local java installation.
– Vipul Chauhan
Jan 3 at 22:22
2
@VipulChauhan The second to last element would belist.get(list.size() - 2)
– shash678
Jan 3 at 22:38
add a comment |
Thanks I wanted to get the second to last element, and I thought using get(list.size() - 1) might be really slow if it was traversing from the start.
– Vipul Chauhan
Jan 3 at 22:20
I frist tried to use getLast().prev() but there was no method :)
– Vipul Chauhan
Jan 3 at 22:21
I am coding on leetcode.com on a ipad which does not have acess to source code completion or a local java installation.
– Vipul Chauhan
Jan 3 at 22:22
2
@VipulChauhan The second to last element would belist.get(list.size() - 2)
– shash678
Jan 3 at 22:38
Thanks I wanted to get the second to last element, and I thought using get(list.size() - 1) might be really slow if it was traversing from the start.
– Vipul Chauhan
Jan 3 at 22:20
Thanks I wanted to get the second to last element, and I thought using get(list.size() - 1) might be really slow if it was traversing from the start.
– Vipul Chauhan
Jan 3 at 22:20
I frist tried to use getLast().prev() but there was no method :)
– Vipul Chauhan
Jan 3 at 22:21
I frist tried to use getLast().prev() but there was no method :)
– Vipul Chauhan
Jan 3 at 22:21
I am coding on leetcode.com on a ipad which does not have acess to source code completion or a local java installation.
– Vipul Chauhan
Jan 3 at 22:22
I am coding on leetcode.com on a ipad which does not have acess to source code completion or a local java installation.
– Vipul Chauhan
Jan 3 at 22:22
2
2
@VipulChauhan The second to last element would be
list.get(list.size() - 2)
– shash678
Jan 3 at 22:38
@VipulChauhan The second to last element would be
list.get(list.size() - 2)
– shash678
Jan 3 at 22:38
add a comment |
Looking at the source code answers the question pretty quickly (the answer is yes):
/**
* Returns the element at the specified position in this list.
*
* @param index index of the element to return
* @return the element at the specified position in this list
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
/**
* Returns the (non-null) Node at the specified element index.
*/
Node<E> node(int index) {
// assert isElementIndex(index);
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
Thanks I was coding on a platform that had no code completion/jump to def, (leetcode on an ipad).
– Vipul Chauhan
Jan 3 at 22:26
add a comment |
Looking at the source code answers the question pretty quickly (the answer is yes):
/**
* Returns the element at the specified position in this list.
*
* @param index index of the element to return
* @return the element at the specified position in this list
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
/**
* Returns the (non-null) Node at the specified element index.
*/
Node<E> node(int index) {
// assert isElementIndex(index);
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
Thanks I was coding on a platform that had no code completion/jump to def, (leetcode on an ipad).
– Vipul Chauhan
Jan 3 at 22:26
add a comment |
Looking at the source code answers the question pretty quickly (the answer is yes):
/**
* Returns the element at the specified position in this list.
*
* @param index index of the element to return
* @return the element at the specified position in this list
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
/**
* Returns the (non-null) Node at the specified element index.
*/
Node<E> node(int index) {
// assert isElementIndex(index);
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
Looking at the source code answers the question pretty quickly (the answer is yes):
/**
* Returns the element at the specified position in this list.
*
* @param index index of the element to return
* @return the element at the specified position in this list
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
/**
* Returns the (non-null) Node at the specified element index.
*/
Node<E> node(int index) {
// assert isElementIndex(index);
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
answered Jan 3 at 22:17


Ryan CogswellRyan Cogswell
5,9481625
5,9481625
Thanks I was coding on a platform that had no code completion/jump to def, (leetcode on an ipad).
– Vipul Chauhan
Jan 3 at 22:26
add a comment |
Thanks I was coding on a platform that had no code completion/jump to def, (leetcode on an ipad).
– Vipul Chauhan
Jan 3 at 22:26
Thanks I was coding on a platform that had no code completion/jump to def, (leetcode on an ipad).
– Vipul Chauhan
Jan 3 at 22:26
Thanks I was coding on a platform that had no code completion/jump to def, (leetcode on an ipad).
– Vipul Chauhan
Jan 3 at 22:26
add a comment |
rx Q XZgBnXysLyj5hZZ8tkwxsm4jLz Z6jMVYw8Kkx0B0fx1ABpDCsxkG7nJvjG0COPrldX ijeiuRu RAB
2
Wouldn't it be fun and easier to just fire up the debugger and verify the behavior?
– Scorpion
Jan 3 at 22:15
Java (as you probably know) is open source. Nothing stops you from finding out.
– PM 77-1
Jan 3 at 22:20