Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Advantages of linked lists over binary trees?

The title is mostly self-explanatory: what are the advantages of linked lists over binary trees? The only case I can think of in which a linked list is more efficient is for iterating over every element, in which case it's still pretty close. It looks like binary trees are faster at both accessing data and inserting new elements. So why use a linked list at all?

like image 781
Michael Dickens Avatar asked Dec 09 '22 17:12

Michael Dickens


1 Answers

If the tail of a linked list is stored, then insertion into a linked list is decidedly faster than insertion into a binary tree. Insertion into a binary tree is O(N) at worst case (O(log N) at best) if it's unbalanced. If it's balanced, then insertions are O(log N), but there is house keeping involved in keeping it balanced. Insertion into a linked list is O(1) if the tail is kept.

Also, as BillyONeal mentioned, a binary tree is usually an associative structure, whereas linked lists are not.

like image 157
P Daddy Avatar answered Jan 13 '23 09:01

P Daddy