CODEWITHSUNDEEP
data-structures
Jawwad Rafiq
Jawwad Rafiq

Reputation: 327

Which one is better , Link-list or Tree, Memory-wise (RAM) ..?

Which one is better , Link-list or Tree, Memory-wise (RAM) ..?

Link-list is a linear structure. Or Tree is Leveled Structure( child-nodes) . Which one is better memory-wise. Not searching-wise.

Upvotes: 0

Views: 1305

Answers (2)

Serge Rogatch
Serge Rogatch

Reputation: 15020

When comparing a linked-list and a tree, memory rarely is to consider because the purposes of these 2 data structures are completely different. In terms of memory linked list can be compared to a vector (an array): because a vector stores items on adjacent memory, it does not need a pointer along with each item so a vector/array consumes less memory. A tree needs a vector of children in each node, while each item in this vector is a pointer to a child node. So a tree consumes at least as much memory as a linked-list because for each node except the root a pointer to that node is stored in its parent.

Upvotes: 1

Mathias Dolidon
Mathias Dolidon

Reputation: 3903

Besides Damien's witty comment : what sort of tree ? Binary ? Red/black ? Ternary ? With a linked-list of children for each node ? Nodes referencing their parent or not ?

Once you chose your data structure, you just look at the overhead for each node. For instance, a singly linked list node's overhead is one pointer to the next element. A simple binary tree node's overhead typically will be two pointers : one two each child. So there you go, simple as that. That particular list would have twice less overhead than that particular tree, only considering the data structure itself.

Upvotes: 1

Related Questions