In this post, we will learn the difference between Tree data structure and Linked List data structure. This is a frequently asked question in interviews for beginners. Let's dive into it.
| Tree | Linked List |
|---|---|
| A Tree is a hierarchical data structure where each node can have multiple children. | A Linked List is a linear data structure where each node can have only one successor. |
| Trees have a "root" node and every other node can be reached from it by following the edges or links between the nodes. | In a linked list, the first node (head) provides a reference to traverse the entire list. |
| In a tree, each node can be linked to multiple nodes to form a hierarchy. | In a linked list, each node is only linked to its next node in the sequence. |
| The nodes in a tree are connected by edges representing the parent-child relationship. | The nodes in a linked list are connected by pointers showing the immediate next node. |
| Trees can be used to represent hierarchical relationships, such as file systems, organization hierarchies, etc. | Linked lists are often used for dynamic memory allocation, implementing stacks and queues, etc. |
| Tree traversal includes depth-first and breadth-first approaches. It can be pre-order, in-order, post-order, or level-order. | Linked list traversal is typically in a single direction (from head to tail), although it can be in both directions in a doubly linked list. |
| Insertion and deletion of nodes in a tree can be complex as it might require rearrangement of multiple nodes. | Insertion and deletion of nodes in a linked list are relatively simple as they mostly involve changing the next pointers. |
| Trees need more memory for storage as each node stores data and references to its child nodes. | Linked lists use less memory as each node only stores its data and a reference to the next node (and the previous node in case of a doubly linked list). |
Example
Let's create an example to illustrate the difference between a binary search tree (Tree) and a linked list (Linked List) in Java.
A binary search tree is a binary tree where each node has at most two child nodes, and the left child is less than or equal to the parent, while the right child is greater than the parent. It allows for efficient searching, insertion, and deletion operations, making it useful for maintaining sorted data.
On the other hand, a linked list is a linear data structure where each element (node) contains a data element and a reference (link) to the next element. It does not maintain any sorting order and is mainly used for simple storage of elements.
Let's see an example:
// Node class for both Tree and Linked List
class Node {
int data;
Node left, right;
Node(int data) {
this.data = data;
this.left = null;
this.right = null;
}
}
public class TreeVsLinkedListExample {
// Binary Search Tree (Tree) example
static Node insert(Node root, int key) {
if (root == null) {
return new Node(key);
}
if (key < root.data) {
root.left = insert(root.left, key);
} else if (key > root.data) {
root.right = insert(root.right, key);
}
return root;
}
// Linked List (Linked List) example
static Node insert(Node head, int data) {
Node newNode = new Node(data);
if (head == null) {
return newNode;
} else {
Node current = head;
while (current.right != null) {
current = current.right;
}
current.right = newNode;
return head;
}
}
// Print the elements of Binary Search Tree (Tree)
static void printTree(Node root) {
if (root != null) {
printTree(root.left);
System.out.print(root.data + " ");
printTree(root.right);
}
}
// Print the elements of Linked List (Linked List)
static void printLinkedList(Node head) {
Node current = head;
while (current != null) {
System.out.print(current.data + " ");
current = current.right;
}
}
public static void main(String[] args) {
// Binary Search Tree (Tree) example
Node treeRoot = null;
treeRoot = insert(treeRoot, 50);
treeRoot = insert(treeRoot, 30);
treeRoot = insert(treeRoot, 70);
treeRoot = insert(treeRoot, 20);
treeRoot = insert(treeRoot, 40);
System.out.println("Binary Search Tree (Tree):");
printTree(treeRoot);
// Linked List (Linked List) example
Node linkedListHead = null;
linkedListHead = insert(linkedListHead, 10);
linkedListHead = insert(linkedListHead, 20);
linkedListHead = insert(linkedListHead, 30);
linkedListHead = insert(linkedListHead, 40);
linkedListHead = insert(linkedListHead, 50);
System.out.println("\nLinked List (Linked List):");
printLinkedList(linkedListHead);
}
}
Output:
Binary Search Tree (Tree):
20 30 40 50 70
Linked List (Linked List):
10 20 30 40 50 Explanation:
In the example, we have created two methods insert for inserting elements into the binary search tree (Tree) and linked list (Linked List). We then create a binary search tree with nodes having data 50, 30, 70, 20, and 40, and a linked list with nodes having data 10, 20, 30, 40, and 50. When we print the elements of the binary search tree, they are printed in sorted order due to their binary search tree property.
In contrast, the elements of the linked list are printed in the same order they were inserted. This demonstrates that the binary search tree maintains a sorted order of elements, whereas the linked list does not.
Comments
Post a Comment