Algorithms and Data Structures Overview

Algorithms and Data Structures Overview

0%

1. Introduction to ADS

When we start learning something new, it is very important to get familiar with the subject of our study first. So let's dive deeper into what we will learn about in this course.

Why Do We Need Algorithms and Data Structures

Why Do We Need Data Structures?

Algorithm Analysis

Challenge: How to Determine Algorithm Complexity

2. List and Array

Arrays and lists serve as foundational data structures in programming, with Python employing them extensively. This section provides an overview of these structures, delving into their concepts and highlighting their implementation nuances within the Python programming language.

Array Data Structure

Basic Array Operations Time Complexity

Challenge: Inserting Elements into the Array

Linked List Data Structure

Basic List Operations Time Complexity

Challenge: Inversing the Order of Elements in the List

Doubly Linked List

3. Advanced Data Structures

There are many applied tasks in which it is necessary to operate with large amounts of structured data and simple data structures such as an array or a linked list may no longer be enough for these purposes. In this section, we'll look at the concept of an abstract data type and how different ADTs allow us to efficiently manage large amounts of data.

Challenge: Using Stack to Find Palindrome

Challenge: Creating Hash Table with String Keys

4. Graphs

In the real world, one often has to deal with tasks in which it is necessary to model complex dependencies between various nodes of a system or domain. Graphs can help us with this. In this section, we will learn what a graph is and how to represent it in computer memory efficiently.

Graph Implementation

Challenge: Graph Traversal Algorithms

Challenge: Balanced Trees

Course Content

Algorithms and Data Structures Overview

Doubly Linked List

The linked list is a versatile data structure, free from the "holes" inherent in arrays.
Manipulating the first element is efficient, but for certain abstract data types like queues, efficient manipulation of the last element and bidirectional traversal are needed. Standard linked lists struggle with accessing the last element, requiring O(N) time complexity.
Doubly linked lists resolve this limitation and offer solutions to various other challenges.


              1234567891011121314151617181920212223
            
from lolviz import *
from IPython.display import display_png

class Node:

  def __init__(self, data):
    self.value = data
    self.next = None
    self.previous = None

# Let's create some nodes
node1 = Node(1)
node2 = Node(2)
node3 = Node(3)

# Then let's couple them into a linked list
node1.next = node2
node2.next = node3
# And don't forget to assign the reference to a previous node
node2.previous = node1
node3.previous = node2

display_png(objviz(node1))

The doubly linked list's nodes contain the references to the next and to the previous elements. Therefore we can access the first and the last item in O(1) constant running time. Time complexity of all other operations for doubly linked list is the same as for the simple linked list.

Everything was clear?

Thanks for your feedback!

Section 2. Chapter 7

some-alt