DEV Community πŸ‘©β€πŸ’»πŸ‘¨β€πŸ’»

Cover image for Introduction to Data Structures and Algorithms With Python
Elkanah Malonza
Elkanah Malonza

Posted on

Introduction to Data Structures and Algorithms With Python

Python provides data types that provides a flexible way to access and organize multiple data. They are called Data Structures. Data Structures are a specialized means of organizing and storing data in computers in such a way that we can perform operations on the stored data more efficiently.
A Data structure is a particular way of organizing data in a computer so that it can be used effectively. It is a specialized format for organizing, processing, retrieving and storing data.
Algorithm on the hand is a set of well-defined instructions in calculation or to solve a particular problem.

The basic Python data structures in Python include:

  1. Lists
  2. Tuples
  3. Sets
  4. Dictionaries

Their some data structures that are user-defined (not part of python data types). They include:

  1. Stack - LIFO
  2. Queues - FIFO
  3. Linked Lists
  4. Hash Tables
  5. Trees
  6. Graphs

1. Lists

A list is a value that contains multiple values in an ordered sequence. A list begins with an opening square bracket and ends with a closing square bracket, []. Values inside the list are also called items which are separated with commas. For example:

subjects = ['Maths', 'Physics', 'Biology', 'Geography', 'History']
num = [1, 2, 3, 4, 5, 6, 7, 8, 9, 0]
Enter fullscreen mode Exit fullscreen mode
  • To get individual values in a List we use Indexes. Example:
subjects = ['Maths', 'Physics', 'Biology', 'Geography', 'History']
# subjects[0] will evaluate to Maths
print(subjects[0]) # Maths 
# subjects[1] will evaluate to Physics
print(subjects[0]) # Physics 
Enter fullscreen mode Exit fullscreen mode

The integer inside the square brackets that follows the list is called an index. The first value in the list is at index 0 , the second value is at index 1 , the third value is at index 2 , and so on.

NOTE: Python will give you an IndexError error message if you use an index that exceeds the number of values in your list value.

  • Lists can also contain other list values.
food = [['tea', 'coffee', 'water'], ['beef', 'pork', 'mutton', 'fish', 'chicken'], ['rice', 'pasta']]
beverage = food[0]
print(beverage) # ['tea', 'coffee', 'water']
# print individual value
print(food[1][3]) # 'fish'
Enter fullscreen mode Exit fullscreen mode

The first index dictates which list value to use, and the second indicates the value within the list value. Example:
food[1][3] # 'fish'

  • negative indexes

You can also use negative integers for the index. The integer value -1 refers to the last index in a list, the value -2 refers to the second-to-last index in a list, and so on. Example:

num = [1, 2, 3, 4, 5, 6, 7, 8, 9, 0]
print(num[-1]) # 0
print(num[-2]) # 9
print(num[-5]) # 6
Enter fullscreen mode Exit fullscreen mode
  • Slicing a List to get a Sub-lists A slice can get several values from a list, in the form of a new list. A slice is typed between square brackets, like an index, but it has two integers separated by a colon.
subjects = ['Maths', 'Physics', 'Biology', 'Geography', 'History']
print(subjects[1:4]) # ['Physics', 'Biology', 'Geography']
Enter fullscreen mode Exit fullscreen mode

The first integer in a slice is the index where the slice starts. The second integer is the index where the slice ends but will not include it.

Leaving out the first index is the same as using 0 , or the beginning of the list. Leaving out the second index is the same as using the length of the list, which will slice to the end of the list.

subjects = ['Maths', 'Physics', 'Biology', 'Geography', 'History']
print(subjects[:3]) # ['Maths', 'Physics', 'Biology']
print(subjects[3:]) # ['Geography', 'History']
Enter fullscreen mode Exit fullscreen mode
  • Changing Values in a List with Indexes
subjects = ['Maths', 'Physics', 'Biology', 'Geography', 'History']
subject[0] = 'Mathematics'
print(subject) # ['Mathematics', 'Physics', 'Biology', 'Geography', 'History']
Enter fullscreen mode Exit fullscreen mode
  • Adding two lists using + operator
core_subjects = ['Maths', 'Physics', 'Biology', 'Geography', 'History']
supplementary_subjects = ['Programming', 'Sports', 'Communication']
subjects = core_subjects + supplementary_subjects
print(subjects)  
['Maths', 'Physics', 'Biology', 'Geography', 'History', 'Programming', 'Sports', 'Communication']
Enter fullscreen mode Exit fullscreen mode
  • Replicating a list using * operator
num = [1, 3, 5]
print(num*3) # [1, 3, 5, 1, 3, 5, 1, 3, 5]
Enter fullscreen mode Exit fullscreen mode
  • Removing Values from Lists with del Statements
subjects = ['Maths', 'Physics', 'Biology', 'Geography', 'History']
del subjects[2]
print(subjects) # ['Maths', 'Physics', 'Geography', 'History']
Enter fullscreen mode Exit fullscreen mode
  • Using for Loops with Lists
subjects = ['Maths', 'Physics', 'Biology', 'Geography', 'History']
for sub in subjects:
    print(sub)
Enter fullscreen mode Exit fullscreen mode
  • The in and not in Operators You can determine whether a value is or isn’t in a list with the in and not in operators.
subjects = ['Maths', 'Physics', 'Biology', 'Geography', 'History']

print('Physics' in subjects) # True

print('Physics' not in subjects) # False

print('Programming' in subjects) # False

print('Programming' not in subjects) # True
Enter fullscreen mode Exit fullscreen mode
  • Getting a List’s Length with len()
subjects = ['Maths', 'Physics', 'Biology', 'Geography', 'History']
print(len(subjects))
Enter fullscreen mode Exit fullscreen mode
  • Multiple Assignment using Lists

You can assign multiple variables with the values in a list in one line of code.

subjects = ['Maths', 'Physics', 'Biology', 'Geography', 'History']
maths, physics, bio, geo, history = subjects
print(geo) # 'Geography'
print (physics) # 'Physics'
Enter fullscreen mode Exit fullscreen mode
  • Converting Types with the list() Functions
line1 = 'hello'
line1_list = list(line1)
print(line1_list) # ['h', 'e', 'l', 'l', 'o']

subjects = ('History', 'Geography', 'Biology', 'Physics', 'Maths')
subjects = list(subjects) # ['History', 'Geography', 'Biology', 'Physics', 'Maths']
Enter fullscreen mode Exit fullscreen mode

List Methods

append() - Adds an item to the end of the list.
clear() - Removes all items from the list, leaving it empty.
copy() - Makes a copy of a list.
count() - Counts how many times an element appears in a list.
extend() - Appends the items from one list to the end of another list.
index() - Returns the index number (position) of an element within a list.
insert() - Inserts an item into the list at a specific position.
pop() - Removes an element from the list, and provides a copy of that item that you can store in a variable.
remove() - Removes one item from the list.
reverse() - Reverses the order of items in the list.
sort() - Sorts the list in ascending order. Put reverse=True inside the parentheses to sort in descending order.

index()

subjects = ['Maths', 'Physics', 'Biology', 'Geography', 'History']
print(subject.index('Physics')) # 1
Enter fullscreen mode Exit fullscreen mode

append()

subjects = ['Maths', 'Physics', 'Biology', 'Geography', 'History']
subject.append('Programming') 
print(subject) # ['Maths', 'Physics', 'Biology', 'Geography', 'History', 'Programming']
Enter fullscreen mode Exit fullscreen mode

insert()

subjects = ['Maths', 'Physics', 'Biology', 'Geography', 'History']
subject.insert('Programming', 1) 
print(subject) # ['Maths', 'Programming', 'Physics', 'Biology', 'Geography', 'History']
Enter fullscreen mode Exit fullscreen mode

remove()

subjects = ['Maths', 'Physics', 'Biology', 'Geography', 'History']
subject.remove('Biology') 
print(subject) # ['Maths', 'Physics', 'Geography', 'History']
Enter fullscreen mode Exit fullscreen mode

NOTE: If the value appears multiple times in the list, only the first instance of the value will be removed.

sort()

# Arrange in alphabetical order
subjects = ['Maths', 'Physics', 'Biology', 'Geography', 'History']
subjects.sort() 
print(subjects) # ['Biology', 'Geography', 'History', 'Maths', 'Physics' ]
Enter fullscreen mode Exit fullscreen mode
# Arrange in numeric order
random_num = [5, 5, 3, 8, 2, 1, 8, 0, 7]
random_num.sort() # [0, 1, 2, 3, 5, 5, 7, 8, 8]
Enter fullscreen mode Exit fullscreen mode
  • You can also pass True for the reverse keyword argument to have sort() sort the values in reverse order.
random_num = [5, 5, 3, 8, 2, 1, 8, 0, 7]
random_num.sort(reverse=True) # [8, 8, 7, 5, 5, 3, 2, 1, 0]
Enter fullscreen mode Exit fullscreen mode
  • you cannot sort lists that have both number values and string values in them, since Python doesn’t know how to compare these values.
  • sort() uses β€œASCIIbetical order” rather than actual alphabetical order for sorting strings. This means uppercase letters come before lower-case letters.
spam = ['Alice', 'ants', 'Bob', 'badgers', 'Carol', 'cats']
spam.sort() # ['Alice', 'Bob', 'Carol', 'ants', 'badgers', 'cats']

Enter fullscreen mode Exit fullscreen mode
  • you need to sort the values in regular alphabetical order, pass str.lower for the key keyword argument in the sort() method call.
spam = ['a', 'z', 'A', 'Z']
spam.sort(key=str.lower) # ['a', 'A', 'z', 'Z']
Enter fullscreen mode Exit fullscreen mode

pop()

subjects = ['Maths', 'Physics', 'Biology', 'Geography', 'History']

# remove last subject
last_subject = subjects.pop()
print(subjects) # ['Maths', 'Physics', 'Biology', 'Geography']
print(last_subject) # 'History'

# remove first subject
first_subject = subjects.pop(0)
print(subjects) # ['Physics', 'Biology', 'Geography']
print(first_subject) # 'Maths' 
Enter fullscreen mode Exit fullscreen mode

count()

num = [5, 7, 8, 5, 3, 8, 5, 2, 1, 8, 5, 7]
num_count = num.count(5)
print(num_count) # 4
Enter fullscreen mode Exit fullscreen mode

extend()

subjects = ['Maths', 'Physics', 'Biology', 'Geography', 'History']
supplementary_subjects = ['Programming', 'Sports', 'Communication']
subjects.extend(supplementary_subjects)
print(subjects) # ['Maths', 'Physics', 'Biology', 'Geography', 'History', 'Programming', 'Sports', 'Communication']
Enter fullscreen mode Exit fullscreen mode

clear()

subjects = ['Maths', 'Physics', 'Biology', 'Geography', 'History']
subjects.clear()
print(subjects) # [ ]
Enter fullscreen mode Exit fullscreen mode

reverse()

subjects = ['Maths', 'Physics', 'Biology', 'Geography', 'History']
subjects.reverse()
print(subjects) # ['History', 'Geography', 'Biology', 'Physics', 'Maths']
Enter fullscreen mode Exit fullscreen mode

copy()

subjects = ['Maths', 'Physics', 'Biology', 'Geography', 'History']
subject_copy = subjects.copy()
print(subject_copy) # ['Maths', 'Physics', 'Biology', 'Geography', 'History']
Enter fullscreen mode Exit fullscreen mode

2. Tuple

A tuple is just an immutable list. In other words, a tuple is a list, but after it’s defined you can’t change it. Tuples are typed with parentheses, ( and ) , instead of square brackets, [ and ]. Example:

subjects = ('History', 'Geography', 'Biology', 'Physics', 'Maths')
num = (5, 7, 8, 5, 3, 8, 5, 2, 1, 8, 5, 7)
Enter fullscreen mode Exit fullscreen mode

List methods and techniques that modified list data won't with tuple but other methods will work:

print(num.count(5)) # 4
print(type(subjects)) # <class 'tuple'>
print(len(num)) # 12
print('Physics' in subjects) # True
Enter fullscreen mode Exit fullscreen mode

Converting to Tuple Types with tuple() Functions

subjects = ['Maths', 'Physics', 'Biology', 'Geography', 'History']
subjects = tuple(subjects)
print(subjects) # ('Maths', 'Physics', 'Biology', 'Geography', 'History')
Enter fullscreen mode Exit fullscreen mode

3. Sets

Python Sets is also a means of organizing data. The difference between a set and a list is that the items in set have no specific order. Even though you may define the set with the items in a certain order, none of the items get index numbers to identify their positions.

To define a set, use curly braces where you would have used square brackets for a list and parentheses for a tuple. For example:

subjects = {'Maths', 'Physics', 'Biology', 'Geography', 'History'}
num = {5, 7, 8, 5, 3, 8, 5, 2, 1, 8, 5, 7}
Enter fullscreen mode Exit fullscreen mode

You can’t change the order of items in a set, so you cannot use .sort() to sort the set or .reverse() to reverse its order. You can use len() to determine size of set and in operator to check if an item exists.

  • add() - You can add a single new item to a set
subjects = {'Maths', 'Physics', 'Biology', 'Geography', 'History'}
subjects.add('Programming')
print(subjects) # {'Maths', 'Physics', 'Biology', 'Geography', 'History', 'Programming'}
Enter fullscreen mode Exit fullscreen mode
  • update() - add multiple items to a set
subjects = {'Maths', 'Physics', 'Biology', 'Geography', 'History'}
subjects.update(['Programming', 'Sports', 'Communication'])
print(subjects) # {'Maths', 'Physics', 'Biology', 'Geography', 'History', 'Programming', 'Sports', 'Communication'}
Enter fullscreen mode Exit fullscreen mode
  • copy() - replicate a set
subjects = {'Maths', 'Physics', 'Biology', 'Geography', 'History'}
subjects_copy = subjects.copy('Programming')
print(subjects_copy) # {'Maths', 'Physics', 'Biology', 'Geography', 'History'}
Enter fullscreen mode Exit fullscreen mode

4. Dictionary

Like a list, a dictionary is a collection of many values, but unlike indexes for lists, indexes for dictionaries can use many different data types, not just integers. Indexes for dictionaries are called keys, and a key with its associated value is called a key-value pair.
In code, a dictionary is typed with braces, {}. Example:

person = {
"name": "Elkanah",
"gender": "Male",
"Height": "5.9 Foot",
"Weight": "67 kg",
}
Enter fullscreen mode Exit fullscreen mode
  • You can access these values through their keys:
print(person["name"]) # Elkanah
print(person["height"]) # 5.9 Foot
Enter fullscreen mode Exit fullscreen mode
  • Unlike lists, items in dictionaries are unordered. It does not matter in what order the key-value pairs are typed in a dictionary:
person = {"name": "Elkanah", "gender": "Male", "Height": "5.9 Foot","Weight": "67 kg",}
person2 = {"Height": "5.9 Foot", "name": "Elkanah", "Weight": "67 kg", "gender": "Male",}

print(person==person1) # True
Enter fullscreen mode Exit fullscreen mode
  • Changing the value of a key in dictionary
person = {"name": "Elkanah", "gender": "Male", "Height": "5.9 Foot","Weight": "67 kg",}
person["name"] = "Malonza"
print(person) # {"name": "Malonza", "gender": "Male", "Height": "5.9 Foot","Weight": "67 kg",}
Enter fullscreen mode Exit fullscreen mode

Dictionary Methods

clear() - Empties the dictionary by remove all keys and values.
copy() - Returns a copy of the dictionary.
fromkeys() - Returns a new copy of the dictionary but with only specified keys and values.
get() - Returns the value of the specified key, or None if it doesn’t exist.
items() - Returns a list of items as a tuple for each key-value pair.
keys() - Returns a list of all the keys in a dictionary.
pop() - Removes the item specified by the key from the dictionary, and stores it in a variable.
popitem() - Removes the last key-value pair.
setdefault() - Returns the value of the specified key. If the key does not exist: insert the key, with the specified value.
update() - Updates the value of an existing key, or adds a new key-value pair if the specified key isn’t already in the dictionary.
values() - Returns a list of all the values in the dictionary.

  • The keys(), values(), and items() Methods - will return list-like values of the dictionary’s keys, values, or both keys and values.
spam = {'color': 'red', 'age': 42}

v = spam.values()
print(v) # dict_values(['red', 42])

k = spam.keys()
print(k) # dict_keys(['color', 'age'])

kv = spam.items()
print(kv) # dict_items([('color', 'red'), ('age', 42)])
Enter fullscreen mode Exit fullscreen mode
  • The get() Method - takes two arguments: the key of the value to retrieve and a fallback value to return if that key does not exist.
picnicItems = {'apples': 5, 'cups': 2}
print(picnicItems.get('cups', 0)) # 2
print(get('cups', 0)) # 2
Enter fullscreen mode Exit fullscreen mode
  • The setdefault() Method - set a value in a dictionary for a certain key only if that key does not already have a value.
spam = {'name': 'Pooka', 'age': 5}

spam.setdefault('color', 'black')
print(spam) # {'color': 'black', 'age': 5, name: 'Pooka'}

spam.setdefault('color', 'white')
print(spam) # {'color': 'black', 'age': 5, name: 'Pooka'}
Enter fullscreen mode Exit fullscreen mode
  • update() method - to add a new item to a dictionary, or to change the value of a current key.
spam = {'name': 'Pooka', 'age': 5}

spam.update({'color': 'black'})
print(spam) # {'color': 'black', 'age': 5, name: 'Pooka'}

spam.update({'color': 'white'})
print(spam) # {'color': 'white', 'age': 5, name: 'Pooka'}
Enter fullscreen mode Exit fullscreen mode
  • copy() method - make a copy of a data dictionary to work with.
spam = {'name': 'Pooka', 'age': 5}
spam_copy = spam.copy()
print(spam_copy) # {name: 'Pooka', 'age': 5}
Enter fullscreen mode Exit fullscreen mode
  • clear() method - remove all key-value pairs from a dictionary without deleting the entire dictionary
spam = {'name': 'Pooka', 'age': 5}
spam.clear()
print(spam) # {}
Enter fullscreen mode Exit fullscreen mode
  • pop() method - Removes the item specified by the key from the dictionary, and stores it in a variable.
spam = {'color': 'Black', 'name': 'Pooka', 'age': 5}
color = spam.pop("color")
print(spam) # {name: 'Pooka', 'age': 5}
print(color) # Black
Enter fullscreen mode Exit fullscreen mode
  • popitem() method -Remove the last key-value pair from a dictionary
spam = {'color': 'Black', 'name': 'Pooka', 'age': 5}
color = spam.popitem()
print(spam) # {name: 'Pooka', 'age': 5}
print(color) # ('age', 5)
Enter fullscreen mode Exit fullscreen mode
  • fromkeys() method - Returns a new copy of the dictionary but with only specified keys and values
spam = {'color': 'Black', 'name': 'Pooka', 'age': 5}
spam1 = dict.fromkeys(spam.keys())
print(spam1) # {'color': None, 'name': None, 'age': None}

results = dict.fromkeys(['Maths', 'Physics', 'Biology', 'Geography', 'History'])
print(results) # {'Maths': None, 'Physics': None, 'Biology': None, 'Geography': None, 'History': None}
Enter fullscreen mode Exit fullscreen mode

5. Stack

A stack is a linear data structure that follows the principle of Last In First Out (LIFO). This means the last element inserted inside the stack is removed. Stack has one end where the insertion and deletion happens i.e. from the top of the stack.
operation in stack data structures

  • push() - Pushing (storing) an element on the stack
  • pop() - Removing (accessing) an element from the stack
  • peek() - get the top data element of the stack, without removing it.
  • isEmpty() - check if stack is empty.
  • isFull() - check if stack is full.

Example:


# Creating a stack
def stack():
    stack = []
    return stack

# Creating an empty stack
def isEmpty(stack):
    return len(stack) == 0

# Adding items into the stack
def push(stack, item):
    stack.append(item)
    print("pushed item: " + item)

# Removing an element from the stack
def pop(stack):
    if (isEmpty(stack)):
        return "stack is empty"
    return stack.pop()

stack = stack()
push(stack, "me")
push(stack, "we")
push(stack, "us")

print("popped item: " + pop(stack))
print("stack after popping an element: ", stack)

'''output
pushed item: me
pushed item: we
pushed item: us
popped item: us
stack after popping an element:  ['me', 'we']
'''

Enter fullscreen mode Exit fullscreen mode

6. Queues

A Queue is a linear data structure that follows the principle of First In First Out (FIFO). This means the first element inserted inside the stack is removed first. Stack has two end where one is for insertion (enqueue) and the other is for deletion (dequeue).

operations in queue data structure

  • enqueue() βˆ’ add (store) an item to the queue.
  • dequeue() βˆ’ remove (access) an item from the queue.
  • peek() βˆ’ Gets the element at the front of the queue without removing it.
  • isFull() βˆ’ Checks if the queue is full.
  • isEmpty() βˆ’ Checks if the queue is empty.

Example:

class Queue:

    def __init__(self):
        self.queue = []

    # Add an element
    def enqueue(self, item):
        self.queue.append(item)

    # Remove an element
    def dequeue(self):
        if len(self.queue) < 1:
            return None

        return self.queue.pop(0)

    # Check the first element in a Queue
    def peek(self):
        if len(self.queue) < 1:
            return None

        return self.queue[0]

    # Check if the Queue is Empty
    def isEmpty(self):
        return len(self.queue) < 1

    # Display  the queue
    def display(self):
        print(self.queue)

    def size(self):
        return len(self.queue)

q = Queue()

q.enqueue(0)
q.enqueue(2)
q.enqueue(0)
q.enqueue(2)
q.enqueue(2)

q.peek()
q.display()

q.dequeue()

print("After removing an element")
q.peek()
q.display()

''' output
0
[0, 2, 0, 2, 2]

After removing an element
2
[2, 0, 2, 2]
'''

Enter fullscreen mode Exit fullscreen mode

7. Linked List

linked list is a linear data structure where data are connected together via links. It consists of nodes where each node contains a data field and a reference(link) to the next node in the list.

Operations in linked list

  • Insertion βˆ’ Adds an element at the beginning of the list.
  • Deletion βˆ’ Deletes an element at the beginning of the list.
  • Display βˆ’ Displays the complete list.
  • Search βˆ’ Searches an element using the given key.
  • Delete βˆ’ Deletes an element using the given key.

class Node:
    def __init__(self, dataval=None):
        self.dataval = dataval
        self.nextval = None


class SLinkedList:
    def __init__(self):
        self.headval = None

    def listprint(self):
        printval = self.headval
        while printval is not None:
            print (printval.dataval)
            printval = printval.nextval

list = SLinkedList()
list.headval = Node("Mon")
e2 = Node("Tue")
e3 = Node("Wed")

# Link first Node to second node
list.headval.nextval = e2

# Link second Node to third node
e2.nextval = e3

list.listprint()
'''output
Mon
Tue
Wed
'''

Enter fullscreen mode Exit fullscreen mode

8. Hash Tables

Hash table is a data structure that implements an associative array abstract data type, a structure that can map keys to values. A hash table uses a hash function to compute an index, also called a hash code, into an array of buckets or slots, from which the desired value can be found.
In a hash table, data is stored in an array format, where each data value has its own unique index value. Access of data becomes very fast if we know the index of the desired data.

Operations in hash tables

  • Search βˆ’ Searches an element in a hash table.
  • Insert βˆ’ inserts an element in a hash table.
  • delete βˆ’ Deletes an element from a hash table.

Example

hashTable = [[],] * 10

def checkPrime(n):
    if n == 1 or n == 0:
        return 0

    for i in range(2, n//2):
        if n % i == 0:
            return 0

    return 1

def getPrime(n):
    if n % 2 == 0:
        n = n + 1

    while not checkPrime(n):
        n += 2

    return n

def hashFunction(key):
    capacity = getPrime(10)
    return key % capacity

def insertData(key, data):
    index = hashFunction(key)
    hashTable[index] = [key, data]

def removeData(key):
    index = hashFunction(key)
    hashTable[index] = 0

insertData(123, "make a circle")
insertData(456, "a big circle")
insertData(789, "like a sufuria")
print(hashTable)

removeData(123)
print(hashTable)

'''output

[[], [], [123, 'make a circle'], [], [], [456, 'a big circle'], [], [], [789, 'like a sufuria'], []]

[[], [], 0, [], [], [456, 'a big circle'], [], [], [789, 'like a sufuria'], []]

'''
Enter fullscreen mode Exit fullscreen mode

9. Trees

Tree represents the nodes connected by edges, Binary tree or binary search tree to be specifically. Binary Tree is a special data structure used for data storage purposes. A binary tree has a special condition that each node can have a maximum of two children.

Terms used in Binary Tree.

  • Path βˆ’ Path refers to the sequence of nodes along the edges of a tree.
  • Root βˆ’ 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.
  • Parent βˆ’ Any node except the root node has one edge upward to a node called parent.
  • Child βˆ’ The node below a given node connected by its edge downward is called its child node.
  • Leaf βˆ’ The node which does not have any child node is called the leaf node.
  • Subtree βˆ’ Subtree represents the descendants of a node.
  • Visiting βˆ’ Visiting refers to checking the value of a node when control is on the node.
  • Traversing βˆ’ Traversing means passing through nodes in a specific order.
  • Levels βˆ’ Level of a node represents the generation of a node. If the root node is at level 0, then its next child node is at level 1, its grandchild is at level 2, and so on.
  • keys βˆ’ Key represents a value of a node based on which a search operation is to be carried out for a node.

Image description

Operations in Binary Trees

  • Insert βˆ’ Inserts an element in a tree/create a tree.
  • Search βˆ’ Searches an element in a tree.
  • Preorder Traversal βˆ’ Traverses a tree in a pre-order manner.
  • Inorder Traversal βˆ’ Traverses a tree in an in-order manner.
  • Postorder Traversal βˆ’ Traverses a tree in a post-order manner.

10. Graphs

A graph is a pictorial representation of a set of objects where some pairs of objects are connected by links. The interconnected objects are represented by points termed as vertices, and the links that connect the vertices are called edges.
Formally, a graph is a pair of sets (V, E), where V is the set of vertices and E is the set of edges, connecting the pairs of vertices.

Terminologies in Graphs

  • Vertex βˆ’ Each node of the graph is represented as a vertex. In the following example, the labeled circle represents vertices. Thus, A to G are vertices. We can represent them using an array as shown in the following image. Here A can be identified by index 0. B can be identified using index 1 and so on.
  • Edge βˆ’ Edge represents a path between two vertices or a line between two vertices. In the following example, the lines from A to B, B to C, and so on represents edges. We can use a two-dimensional array to represent an array as shown in the following image. Here AB can be represented as 1 at row 0, column 1, BC as 1 at row 1, column 2 and so on, keeping other combinations as 0.
  • Adjacency βˆ’ Two node or vertices are adjacent if they are connected to each other through an edge. In the following example, B is adjacent to A, C is adjacent to B, and so on.
  • Path βˆ’ Path represents a sequence of edges between the two vertices. In the following example, ABCD represents a path from A to D.

Image description

Operations in graphs

  • Add Vertex βˆ’ Adds a vertex to the graph.
  • Add Edge βˆ’ Adds an edge between the two vertices of the graph.
  • Display Vertex βˆ’ Displays a vertex of the graph.

Top comments (0)

Join 900k+ Developers on DEV

You'll see more of the content that brought you here.