Pathifinding

[mirhagk]

A linked list is a very small subset of trees in theory. In implementation there are all sorts of optimizations you can make with a linked list that don't exist with trees. First of all not having an array, which halves the number of memory jumps you need to traverse the list, you can also optimize the traversal since there is only one next node. You can have doubly linked lists with only one pointer stored, which is a XOR of the previous one. There are even more aggressive optimizations you could make (such as having the last element point to a special function that stops the enumeration, rather than having if(pointer==0) checks the entire time) if you really wanted to with linked lists.

The concepts are similar, but linked lists are for vastly different purposes than trees, and are a much simpler concept to learn than trees.

[Dreadnought]

Raknarg wrote:

Are you telling me a tree is not a linked list? It is a list, that is linked in a tree-like fashion.

I have never seen a shopping list in binary tree form. I doubt anyone, even you, would consider that a list.

A linked list is a group of node representing a sequence. Each node will contain data and a pointer to the following (and perhaps previous) node. The nodes are linked together by these pointers hence it is a linked list.

A tree structure has a broader definition. A tree is a group of nodes each with 0 or more children and a single parent. Hence as was stated earlier, a linked list can be regarded as a unary tree.

As you can see, this means that a linked list is also a tree, but a tree is not always a linked list. In particular, a binary tree is definitely not a linked list.

If you must put them under a common name, trees and linked lists are examples of abstract data types.

[Raknarg]

Of course their purposes are different, but the concept is the same. That was my point.

@Dreadnought thanks. And yes, I do consider that a list. Although I have difficulty explaining my own thinking... I'm probably being too abstract for myself. You're right.

[Insectoid]

Quote:

Of course their purposes are different, but the concept is the same. That was my point.

A linked list is a tree, but a tree is not a linked list. The same way a square is a rectangle, but a rectangle is not always a square.

[Raknarg]

Yeah, I didn't say they were the same thing. A square and a rectangle are both quadrilaterals with similar properties. If you understand one shape, you will likely understand another although they are different. In fact, you might be able to understand a cube, although it is more complex, because they have similar properties, they can be considered the same thing, even though they are not.

[Insectoid]

Quote:

That [your tree] was just an example of a linked list application.

[mirhagk]

@Raknarg it was more like giving some one a cube to teach them about squares. Sure the concepts are there, but it's overkill, and too much to take in at once.

[Raknarg]

It wasn't to be used as a method of teaching, it was an example of application.