What is Linked List?

A Linked List is a data structure used for storing collections of data. A linked list has the following properties:

● Successive elements are connected by pointers.

● Can grow or shrink in size during the execution of a program.

● Can be made just as long as required (until systems memory exhausts).

● Does not waste memory space (but takes some extra memory for pointers). It allocates memory as the list grows.

Basic Properties of Linked List:

● Each element or node of a list is comprising of two items:

○ Data

○ Pointer(reference) to the next node.

● In a Linked List, the elements are not stored at contiguous memory locations.

● The first node of a linked list is known as Head.

● The last node of a linked list is known as Tail.

● The last node has a reference to null.

Representation of a Linked List

This representation of a linked list depicts that each node consists of two fields. The first field consists of data, and the second field consists of pointers that point to another node.

Here, the start pointer stores the address of the first node, and at the end, there is a null pointer that states the end of the Linked List.

Creation of Node and Declaration of Linked Lists

(JAVA)

public class Node<T> {

T data;

Node<T> next;

Node(T data){

this.data = data;

next = null;

}

}

Types of Linked List

● Singly-Linked List: Generally “linked list” means a singly linked list. Each node contains only one link which points to the subsequent node in the list.

● Doubly-Linked List: It’s a two-way linked list as each node points not only to the next pointer but also to the previous pointer.

● Circular-Linked List: There is no tail node i.e., the next field is never null and the next field for the last node points to the head node.

● Circular Doubly-Linked List: Combination of both Doubly linked list and circular linked list.

Essential Operations on Linked Lists

• Traversing: To traverse all nodes one by one.
• Insertion: To insert new nodes at specific positions.
• Deletion: To delete nodes from specific positions.
• Searching: To search for an element from the linked list

A. Insertion of A Node in Linked List (Iteratively)

(JAVA)

public static Node<Integer> insert(Node<Integer> head, int data, int pos){

Node<Integer> newNode = new Node<Integer>(data);

if(pos == 0){

newNode.next = head;

return newNode;

}

int i = 0;

Node<Integer> temp = head;

while(i < pos — 1){

temp = temp.next;

i++;

}

newNode.next = temp.next;

temp.next = newNode;

return head;

}

B. Insertion of Node in Linked List (Recursively)

(JAVA)

public static LinkedListNode<Integer> insert(LinkedListNode<Integer> head,int pos,int elem){

if (pos==0){

LinkedListNode<Integer> newNode = new LinkedListNode<Integer>(elem);

newNode.next=head;

return newNode;

}

if (head==null){

return head;

}

head.next=insert(head.next, pos-1, elem);

return head;

}

C. Deletion of A Node in Linked List

(JAVA)

public static LinkedListNode<Integer> deleteNodeRec(LinkedListNode<Integer> head, int pos) {

if (head==null){

return head;

}

if (pos==0){

head=head.next;

return head;

}

LinkedListNode<Integer> ans =deleteNodeRec(head.next, pos-1);

head.next=ans;

return head;

}

Why use Linked List over Array?

Till now, we were using array data structure to organize the group of elements that are to be stored individually in the memory. However, Array has several advantages and disadvantages which must be known in order to decide the data structure which will be used throughout the program.

Array contains following limitations:

1. The size of array must be known in advance before using it in the program.
2. Increasing size of the array is a time taking process. It is almost impossible to expand the size of the array at run time.
3. All the elements in the array need to be contiguously stored in the memory. Inserting any element in the array needs shifting of all its predecessors.

Linked list is the data structure which can overcome all the limitations of an array. Using linked list is useful because,

1. It allocates the memory dynamically. All the nodes of linked list are non-contiguously stored in the memory and linked together with the help of pointers.
2. Sizing is no longer a problem since we do not need to define its size at the time of declaration. List grows as per the program’s demand and limited to the available memory space.

I hope this blog gives you a clear understanding about linked list in data structures. If this blog helps you understand the concept so share it with your friends and feel free to share your views and drop feedback about the blog. Drop the claps if you liked the blog.

Hit the follow button for more such content and stay connected to know about more data structures.

Linked List-Data Structure was originally published in Nerd For Tech on Medium, where people are continuing the conversation by highlighting and responding to this story.

What is Tree?

A tree data structure is a non-linear data structure because it does not store in a sequential manner. It is a hierarchical structure consisting of a collection of nodes such that each node of the tree stores a value and a list of references to other nodes (the “children”).

Why we need Tree as Data-Structure?

Other data structures such as arrays, linked list, stack, and queue are linear data structures that store data sequentially. In order to perform any operation in a linear data structure, the time complexity increases with the increase in the data size. But, it is not acceptable in today’s computational world.

Different tree data structures allow quicker and easier access to the data as it is a non-linear data structure.

Why Tree is considered a non-linear Data-Structure?

The data in a tree are not stored in a sequential manner i.e., they are not stored linearly. Instead, they are arranged on multiple levels or we can say it is a hierarchical structure. For this reason, the tree is considered to be a non-linear data structure.

Basic Terminologies in Tree Data-Structure:

• Child Node: If the node is a descendant of any node, then the node is known as a child node. Like E, F, G are the children of L.
• Root Node: The node at the top of the tree is called root. There is only one root per tree and one path from the root node to any node. Example: P is the root node.
• Edge: It is the link between any two nodes.
• Leaf Node: The node which does not have any child node is called the leaf node.
• Sub-tree: Sub tree represents the descendants of a node.
• Descendant: The immediate successor of the given node is known as a descendant of a node. Like descendants of L are E, F, and G.
• Sibling: Children of the same parent node are called siblings.

Example of Tree Data-Structure

Here,

Node A is the root node

D is the parent of H and I

F and G are the siblings

H, I, F and G are the leaf nodes

Binary Search Tree Representation

Binary Search tree exhibits a special behavior. A node’s left child must have a value less than its parent’s value and the node’s right child must have a value greater than its parent value.

Implementation of Tree Node

(JAVA)

import java.util.ArrayList;

public class TreeNode<T>{

public T data ;

public ArrayList<TreeNode<T>> children;

public TreeNode( T data){

this.data=data;

children=new ArrayList<>();

}

}

Basic Operations

The basic operations that can be performed on a binary search tree data structure, are the following −

1. Insert − Inserts an element in a tree/create a tree.
2. Search − Searches an element in a tree.
3. Preorder Traversal − Traverses a tree in a pre-order manner.
4. In-order Traversal − Traverses a tree in an in-order manner.
5. Post-order Traversal − Traverses a tree in a post-order manner.

Types of Tree Data-Structures

The different types of tree data structures are as follows:

1. General tree

A general tree data structure has no restriction on the number of nodes. It means that a parent node can have any number of child nodes.

2. Binary tree

Here, binary name itself suggests two numbers, i.e., 0 and 1. In a binary tree, each node in a tree can have utmost two child nodes.

3. Balanced tree

If the height of the left sub-tree and the right sub-tree is equal or differs at most by 1, the tree is known as a balanced tree.

Properties of Tree Data-Structure

I. Recursive data structure: The tree is also known as a recursive data structure. A tree can be defined as recursively because the distinguished node in a tree data structure is known as a root node.

II. Number of edges: If there are n nodes, then there would n-1 edges. Each arrow in the structure represents the link or path.

III. Depth of node x: The depth of a node is the number of edges from the root to the node.

IV. Height of node x: The height of a node is the number of edges from the node to the deepest leaf (that is the longest path from the node to a leaf node).

Applications of Tree Data-Structure:

The applications of tree data structures are as follows:

1. Spanning trees: It is the shortest path tree used in the routers to direct the packets to the destination.
2. Binary Search Tree: It is a type of tree data structure that helps in maintaining a sorted stream of data.
3. Heap: It is also a tree data structure implemented using arrays. It is used to implement priority queues.
4. Tries: It is a special kind of tree that is used to store the dictionary. It is a fast and efficient way for dynamic spell checking.
5. Organize data: It is used to organize data for efficient insertion, deletion and searching. For example, a binary tree has a log N time for searching an element.

I hope this blog gives you a clear understanding about trees in data structures. If this blog helps you understand the concept so share it with your friends and feel free to share your views and drop feedback about the blog. Drop the claps if you liked the blog.

Hit the follow button for more such content and stay connected to know about more data structures.

If this post was helpful, please click the clap 👏 button below a few times to show your support for the author 👇

🚀Developers: Learn and grow by keeping up with what matters, JOIN FAUN.

Trees-Data Structure was originally published in FAUN.dev() 🐾 on Medium, where people are continuing the conversation by highlighting and responding to this story.

In this blog, we will discuss one of the data structures i.e. Graphs

A Graph is a non-linear data structure that consists of nodes and edges. The nodes are sometimes referred to as vertices and edges are the lines that connect any two nodes or vertices in the graph.

A more technical definition could be:

“A Graph is a pair of sets. G = (V, E). V is the set of vertices. E is a set of edges. E is made up of pairs of elements from V (unordered pair)”

Graphs are used to solve many real-life problems. Graphs are used to represent networks. The networks may include paths in a city or telephone network or circuit network. Graphs are also used on social networks like LinkedIn, and Facebook.

Graph Terminology

• Path: It is the sequence of vertices in which each pair of successive vertices is connected by an edge.
• Cycle: It is a path that starts and ends on the same vertex.
• Simple Path: It is a path that does not cross itself that is, no vertex is repeated (except the first and the last). Also, simple paths do not contain cycles.
• Length of a Path: It is the number of edges in the path. Sometimes it’s the sum of weights of the edges also in case of weighted graphs.
• Degree of a Vertex: It is the number of edges that are incident to the vertex.

Now that we have understood what graph data structure is and its terminology, so let’s move ahead and see how we can represent graphs.

Graph and its representations

A graph is a data structure that consists of the following two components:

1. A finite set of vertices also called as nodes.
2. A finite set of ordered pair of the form (u, v) called as edge. The pair is ordered because (u, v) is not the same as (v, u) in case of a directed graph (di-graph). The pair of the form (u, v) indicates that there is an edge from vertex u to vertex v. The edges may contain weight/value/cost.

The following two are the most commonly used representations of a graph.
1. Adjacency Matrix
2. Adjacency List
There are other representations also like, Incidence Matrix and Incidence List. The choice of graph representation is situation-specific. It totally depends on the type of operations to be performed and ease of use.

Adjacency Matrix:

Adjacency Matrix is a 2D array of size V x V where V is the number of vertices in a graph. Let the 2D array be adj[][], a slot adj[i][j] = 1 indicates that there is an edge from vertex i to vertex j. Adjacency matrix for undirected graphs is always symmetric. Adjacency Matrix is also used to represent weighted graphs. If adj[i][j] = w, then there is an edge from vertex i to vertex j with weight w.

The adjacency matrix for the above example graph is:

Pros: Representation is easier to implement and follow. Removing an edge takes O (1) time.

Cons: Consumes more space O (N²). Even if the graph is sparse (contains less number of edges), it consumes the same space.

Types of Graph

Following are the different types of graph:

1. Weighted Graph

A weighted graph is a graph in which edges have a weight. So when I say edges have a weight, what I mean to say is that they have some numbers which typically shows the cost of traversing in a graph. When we are concerned with the minimum cost of traversing the graph then what we do is find the path that has the least sum of those weights.

Example: weights can be the distances between cities or can be the fare of traveling.

Example of a Weighted Graph

2. Unweighted Graph

Unweighted graph is a graph in which edges have no weight. In such a case, edges simply show connections.

Example: edges can show the path or route between cities.

Example of an Unweighted Graph

3. Undirected Graph

These type of graphs have no implied direction on edges between the nodes. Edge can be traversed in either direction.

Example of a Undirected Graph

4. Null Graph

A graph is known as a null graph if there are no edges in the graph.

5. Trivial Graph

Graph having only a single vertex, it is also the smallest graph possible.

6. Regular Graph

The graph in which the degree of every vertex is equal to the other vertices of the graph. Let the degree of each vertex be K then the graph

7. Complete Graph

The graph in which from each node there is an edge to each other node.

Tree v/s Graph

Trees are the restricted types of graphs, just with some more rules. Every tree will always be a graph but not all graphs will be trees. Linked List, Trees and Heaps all are special cases of graphs.

I hope this blog gives you a clear understanding about graphs in data structures. If this blog helps you understand the concept so share it with your friends and feel free to share your views and drop feedback about the blog. Drop the claps if you liked the blog.

Hit the follow button for more such content and stay connected to know about more data structures.

Graph — Data Structure was originally published in CodeX on Medium, where people are continuing the conversation by highlighting and responding to this story.