Understanding Tree and Linked List Data Structures
A tree is a nonlinear hierarchical data structure comprising a collection of entities known as nodes. It connects each node in the tree data structure using edges, both directed and undirected.
General Tree
The general tree is a type of tree where there are no constraints on the hierarchical structure.
Tree Traversal
Traversal of the tree in data structures is a process of visiting each node and printing its value. There are three ways to traverse a tree data structure.
Binary Search Tree
A binary search tree is a non-linear data structure in which one node is connected to n number of nodes. It is a node-based data structure. A node can be represented in a binary search tree with three fields: data part, left-child, and right-child. A node can be connected to at most two child nodes in a binary search tree, so the node contains two pointers (left child and right child pointer). Every node in the left subtree must contain a value less than the value of the root node, and the value of each node in the right subtree must be bigger than the value of the root node.
Linked Lists
Linked Lists are data structures consisting of a collection of linear data elements. Each of the data elements is known as a “Node”. The chain of nodes, containing one or more values and a pointer to the next node in the chain, is a Linked List. This data structure does not store its elements in consecutive memory locations but is stored in random locations. Not only this, but it allows users to add any number of elements to the list, thus removing the restrictions of arrays.
Memory Representation of Linked Lists
In memory, the linked list is stored in scattered cells (locations). The memory for each node is allocated dynamically, meaning as and when required. So, the Linked List can increase as per the user’s wish, and the size is not fixed; it can vary.
- Simple Linked List: Item navigation is forward only.
- Doubly Linked List: Items can be navigated forward and backward.
- Circular Linked List: The last item contains a link to the first element as next, and the first element has a link to the last element as previous.
Applications of Linked Lists
- Dynamic data structures such as stacks and queues can be implemented using a linked list and several other common abstract data types, including lists and associative arrays.
- Many modern operating systems use doubly linked lists to maintain references to active processes, threads, and other dynamic objects.
- A hash table may use linked lists to store the chains of items that hash to the same position in the hash table.
- A binary tree can be seen as a type of linked list where the elements are themselves linked lists of the same nature. The result is that each node may include a reference to the first node of one or two other linked lists, which, together with their contents, form the sub-trees below that node.
Advantages of Linked Lists
- They are dynamic in nature, which allocates the memory when required.
- Insertion and deletion operations can be easily implemented.
- Stacks and queues can be easily executed.
- Linked Lists reduce the access time.
Disadvantages of Linked Lists
- Memory is wasted as pointers require extra memory for storage.
- No element can be accessed randomly; it has to access each node sequentially.
- Reverse Traversing is difficult in a linked list.
Why Use Linked Lists?
Arrays can be used to store linear data of similar types, but arrays have the following limitations:
- The size of the arrays is fixed: So, we must know the upper limit on the number of elements in advance. Also, generally, the allocated memory is equal to the upper limit irrespective of the usage.
- Inserting a new element in an array of elements is expensive because room has to be created for the new elements, and to create room, existing elements have to be shifted. But in a Linked List, if we have the head node, then we can traverse to any node through it and insert a new node at the required position.