Linked and binary lists

I was wondering when you should actually use these lists? or when you should want to avoid them? Thanks for helping me try to sort out these concpets

I take it you mean a binary tree, rather than a binary list.

The question of what you use when is one of those interesting questions that one can spend a lot of time debating.

First of all, many of the problems where linked lists are involved can be solved with the standard vector template class.

Linked lists are useful when you want to keep large objects that are usually added/removed from one or the other end of the list, you don't often need to search the list to find something. It is particularly useful if the items stored are fairly large, rather than many small objects (say, a linked list of int's is a bad thing, whilst a linked list of 1KB data items may be a much better choice).

Binary trees are useful if you need to store and find things in sorted order - although inserting in a linked list is easy, to search it is linear to the number of elements, whilst a binary tree takes log2(n) operations to search, so a 1000 entry binary tree should take 10 searches to find the right entry [1].

Note on performance: If the code spends a lot of it's time actually traversing the data in the list/tree, then one of the concerns will be that the nodes will not be in consecutive memory, so the caching and processors prefetch mechanisms will not work very well. Vectors that are implemented using large chunks of contiguous memory will give better performance from that perspective.

[1] This assumes that the tree is balanced. If you insert items that are already sorted into a binary tree, it will deteriorate to a linked list unless it's a "balanced binary tree".

--
Mats

I think he means skip lists.

Quote:

---

Originally Posted by indigo0086

I think he means skip lists.

---

And someone else will think he means doubly-linked-list. He needs to clarify!

Heh sorry I meant binary trees. I never heard of skip lists though. So when do you know when an object is too big for a vector?

I don't think it works that way. I think the biggest concern with data structures is the number of elements in a data structure, how they are organized, the speed of performing operations on the ds and it's elements, and things of that sort. Big objects will have to be stored in memory some way or another.

One of the reasons I mention "large objects" is that if you insert or delete things in the middle of a vector, the vector content will have to be shuffled. Naturally, large amounts of data will require a larger amount of time move the data in the vector around.

In the linked list case, an insertion or removal is independent of the amount of data stored in the list in the sense that there's no movement of data when inserting - just two pointer writes.

Yes, all the data needs to be stored somewhere, but if the data isn't shuffled around, then it's a benefit.

The drawback of linked lists comes with traversing them - there's really no way to search them cleverly - you just have to start at one end and search until you find what you're looking for (or know it's not in the list, if that's the case - either end of the list or you know from the comparison that you've gone past the point of finding it if it's a sorted list).

Binary trees, as long as they are in reasonable balance (not all the entries are in one long linked list on the left or right side of the tree), the searching is faster. Deleting out of binary trees can be a bit tricky too.

Both binary trees and linked lists have a drawback when used for LARGE number of items, particularly if the items are small, since the overhead of looking at the link for the next item is notable. In these cases, a vector or similar is definitely the better case.

--
Mats