Question

Even though linked lists are the simplest data structures, you can build with them complicated networks, trees and graphs. Please do a research and share your findings with us. Pay special attention to include their time complexities. It is not required but a couple of code snippets would look nice in the examples.

Answer 1

For tree,

Binary Tree –
In a binary tree, a node can have maximum two children.

Searching: Searching in binary tree has worst case complexity of O(n).

Insertion: Insertion in binary tree has worst case complexity of O(n).

Deletion: Deletion in binary tree has worst case complexity of O(n).

Binary Search Tree (BST) –
BST is a special type of binary tree in which left child of a node has value less than the parent and right child has value greater than parent.

Searching: Searching in binary search tree has worst case complexity of O(n). In general, time complexity is O(h) where h is height of BST.

Insertion: Worst case complexity of O(n). In general, time complexity is O(h).

Deletion: Deletion in binary tree has worst case complexity of O(n). In general, time complexity is O(h).

AVL/ Height Balanced Tree –
AVL tree is binary search tree with additional property that difference between height of left sub-tree and right sub-tree of any node can’t be more than 1.

Searching: Searching in AVL tree has worst case complexity of O(log2n).
Insertion: Worst case complexity is O(log2n).

Deletion: Deletion in binary tree has worst case complexity of O(log2n).

------------------------------------------------------------------

For Graph (ADJACENCY LIST)

Simple c++ code for graph

// A simple representation of graph using STL
#include<bits/stdc++.h>
using namespace std;

// A utility function to add an edge in an
// undirected graph.
void addEdge(vector<int> adj[], int u, int v)
{
   adj[u].push_back(v);
   adj[v].push_back(u);
}

// A utility function to print the adjacency list
// representation of graph
void printGraph(vector<int> adj[], int V)
{
   for (int v = 0; v < V; ++v)
   {
       cout << "\n Adjacency list of vertex "
           << v << "\n head ";
       for (auto x : adj[v])
       cout << "-> " << x;
       printf("\n");
   }
}

// Driver code
int main()
{
   int V = 5;
   vector<int> adj[V];
   addEdge(adj, 0, 1);
   addEdge(adj, 0, 4);
   addEdge(adj, 1, 2);
   addEdge(adj, 1, 3);
   addEdge(adj, 1, 4);
   addEdge(adj, 2, 3);
   addEdge(adj, 3, 4);
   printGraph(adj, V);
   return 0;
}

Pros: Saves space O(|V|+|E|) . In the worst case, there can be C(V, 2) number of edges in a graph thus consuming O(V^2) space. Adding a vertex is easier.

Cons: Queries like whether there is an edge from vertex u to vertex v are not efficient and can be done O(V).