Как программисты, мы пишем код, чтобы инструктировать компьютеры обрабатывать, хранить, редактировать и извлекать данные. Структура данных — это метод организации данных, обеспечивающий эффективное хранение и восстановление информации.
Каждая компьютерная программа должна хранить данные в различных структурах данных для обработки. Современные языки программирования и фреймворки настолько сложны, что когда-то распространенное программирование структур данных в основном абстрагируется за кулисами, чтобы облегчить жизнь программистам. Снижение сложности кода снижает вероятность появления в нем ошибок!
Тем не менее бывают случаи, когда мы, программисты, можем писать более элегантные программы и API, если знаем основы алгоритмов и структур данных.
Здесь я объясняю 5 структур данных, которые каждый программист должен знать и преуспеть.
1. Связанный список
Связанные списки — самая простая и одна из самых распространенных структур данных. Связанный список — это линейный набор элементов данных, порядок которых не определяется их физическим размещением в памяти. Вместо этого каждый элемент указывает на следующий.
Рассмотрим простой связанный список, показанный ниже.
Каждое значение или данные связаны с указателями.
Список ссылок состоит из узлов и указателей, как показано ниже.
У узла есть значение (данные) и указатель, указывающий на следующий узел, к которому он подключается. Указатели — это просто ссылка на ячейку памяти значения или данных.
Существует два основных типа связанных списков
а) Односвязные списки
б) двусвязный список
а) Односвязные списки
Односвязные списки содержат узлы, которые имеют поле данных, а также указатель («next_node» в нашем коде ниже), который указывает на следующий узел в строке узлов. Операции, которые можно выполнять над односвязными списками, включают вставку, удаление и обход.
Теперь давайте напишем код для создания объекта node. Вы можете рассматривать этот объект как шаблон для создания узлов. Этот фрагмент кода может использоваться другими программами для создания и инициализации узлов.
class Node(object):
def __init__(self, data, next_node=None):
self.data = data
self.next_node = next_node
def get_data(self):
return self.data
def get_next_node(self):
return self.get_next_node
def set_data(self, data):
self.data = data
def set_next_node(self, next_node):
self.next_node = next_node
Теперь давайте создадим класс односвязного списка, используя объект Node, как показано в шаблоне ниже.
И код выглядит следующим образом:
class LinkedList(object):
def __init__(self, next_node=None):
self.next_node = next_node
self.size = 0
def get_size(self):
return self.size
def get_points_to(self):
return self.get_points_to
def add_node(self, data):
new_node = Node(data, self.next_node)
self.next_node = new_node
self.size += 1
return str(data) + " added to the linked list"
def print_node(self):
current_node = self.next_node
while current_node:
print (current_node.data)
current_node = current_node.next_node
Теперь давайте воспользуемся приведенным выше объектом связанного списка, чтобы создать связанный список с данными, подобными приведенному ниже шаблону.
Код
my_linked_list = LinkedList()
print ("Inserting data")
print (my_linked_list.add_node(15))
print (my_linked_list.add_node(4))
print (my_linked_list.add_node(26))
print ("Printing Linked List Data")
my_linked_list.print_node()
print ("Size is")
print(my_linked_list.get_size())
print ("Head currently is at")
print(my_linked_list.next_node.data)
Выход будет таким
# Output Inserting data 15 added to the linked list 4 added to the linked list 26 added to the linked list Printing Linked List Data 26 4 15 Size is 3 Head currently is at 26
б) двусвязный список
Двусвязный список — это связанная структура данных, состоящая из набора последовательно связанных узлов. Каждый узел содержит три поля: два поля ссылок (ссылки на предыдущий и следующий узел в последовательности узлов) и одно поле данных.
Теперь давайте напишем код для создания объекта узла для двусвязного списка. Вы можете рассматривать этот объект как шаблон для создания узлов. Этот фрагмент кода может использоваться другими программами для создания и инициализации узлов.
class Node(object):
def __init__(self, data=None, previous_node=None, next_node=None):
self.data = data
self.previous_node = previous_node
self.next = next_node
def __repr__(self):
return repr(self.data)
def get_data(self):
return self.data
def set_data(self, data):
self.data = data
def get_next_node(self):
return self.get_next_node
def get_previous_node(self):
return self.get_next_node
def set_next_node(self, previous_node):
self.previous_node = previous_node
Теперь давайте создадим класс двусвязного списка, используя объект Node.
class DoublyLinkedList(object):
def __init__(self):
self.head = None
def __repr__(self):
# Return a string representation of the list.
nodes = []
curr = self.head
while curr:
nodes.append(repr(curr))
curr = curr.next
return '[' + ', '.join(nodes) + ']'
def prepend(self, data):
#Insert a new element at the beginning of the list.
new_head = Node(data=data, next_node=self.head)
if self.head:
self.head.prev = new_head
self.head = new_head
def append(self, data):
# Insert a new element at the end of the list.
if not self.head:
self.head = Node(data=data)
return
curr = self.head
while curr.next:
curr = curr.next
curr.next = Node(data=data, previous_node=curr)
def find(self, key):
"""
Search for the first element with `data` matching
`key`. Return the element or `None` if not found.
"""
curr = self.head
while curr and curr.data != key:
curr = curr.next
return curr # Will be None if not found
def remove_elem(self, node):
# Unlink an element from the list.
if node.prev:
node.prev.next = node.next
if node.next:
node.next.prev = node.prev
if node is self.head:
self.head = node.next
node.prev = None
node.next = None
def remove(self, key):
# Remove the first occurrence of `key` in the list.
elem = self.find(key)
if not elem:
return
self.remove_elem(elem)
def reverse(self):
# Reverse the list in-place.
curr = self.head
prev_node = None
while curr:
prev_node = curr.prev
curr.prev = curr.next
curr.next = prev_node
curr = curr.prev
self.head = prev_node.prev
Давайте проверим приведенный выше двусвязный список.
doubly_linked_list = DoublyLinkedList()
print(doubly_linked_list)
print("Insert a new element 10 at the beginning of the Doubly Linked List")
doubly_linked_list.prepend(10)
print(doubly_linked_list)
print("Insert a new element 23 at the beginning of the Doubly Linked List")
doubly_linked_list.prepend(23)
print(doubly_linked_list)
print("Insert a new element 10 at the end of the Doubly Linked List")
doubly_linked_list.append(7)
print(doubly_linked_list)
print("Unlink (remove) element 10 from the Doubly Linked List")
doubly_linked_list.remove(10)
print(doubly_linked_list)
Вывод вышеуказанной программы:
# Output [] Insert a new element 10 at the beginning of the Doubly Linked List [10] Insert a new element 23 at the beginning of the Doubly Linked List [23, 10] Insert a new element 10 at the end of the Doubly Linked List [23, 10, 7] Unlink (remove) element 10 from the Doubly Linked List [23, 7]
Производительность связанного списка
Ниже приведены показатели производительности нотации Big O для связанного списка.
Логарифмическая производительность связанного списка с точки зрения временной сложности будет выглядеть следующим образом:
Доступ и поиск элементов в связанном списке будут масштабироваться линейно, в то время как вставка и удаление связанного списка являются постоянными с точки зрения временной сложности, даже если количество элементов в связанном списке значительно увеличивается.
2. Стек
Стек — это тип данных, представляющий собой набор элементов, расположенных один над другим, как стопка тарелок.
Есть две основные операции, которые мы можем выполнять со стеком.
я) толкать
ii) поп
я) толкнуть
push добавляет элемент в стек
ii) поп
pop удаляет самый последний элемент из стека.
Код для создания шаблона стека
class Stack (object):
def __init__(self):
self.items = []
def is_empty(self):
return self.items == []
def push(self, item):
self.items.append(item)
def pop(self):
return self.items.pop()
def peek(self):
return self.items[len(self.items) - 1]
def size(self):
return len(self.items)
def print_items(self):
print(self.items)
Теперь давайте напишем код для создания объекта стека, используя приведенный выше шаблон стека.
Стек вначале пуст
# Create a stack Object my_stack = Stack() # Stack is empty at the beginning print(s.is_empty())
Теперь давайте поместим элемент (пример 26) в стек.
# Push 26 to the empty stack my_stack.push(26)
Теперь нажмите больше элементов
# Push more elements to the stack my_stack.push(4) my_stack.push(36) my_stack.push(81) my_stack.push(15)
Просмотр элементов в стеке
s.print_items()
Полный код, как показано ниже
s.push(4)
s.push(36)
s.push(81)
s.push(15)
print(s.peek())
s.print_items()
print(s.size())
print("Is the stack empty? %s" % s.is_empty())
s.push(8.4)
s.print_items()
print(s.pop())
print(s.pop())
print(s.size())
s.print_items()
print("Is the stack empty? %s" % s.is_empty())
print(s.pop())
print(s.pop())
print(s.pop())
print(s.pop())
s.print_items()
print("Is the stack empty? %s" % s.is_empty())
Выход
Is the stack empty? True 15 [26, 4, 36, 81, 15] 5 Is the stack empty? False [26, 4, 36, 81, 15, 8.4] 8.4 15 4 [26, 4, 36, 81] Is the stack empty? False 81 36 4 26 [] Is the stack empty? True
Производительность стека
Ниже приведены показатели производительности нотации Big O для стека.
Производительность стека с точки зрения временной сложности будет выглядеть следующим образом.
Доступ и поиск элементов в стеке также будут масштабироваться линейно. Вставка и удаление элементов в стеке постоянны с точки зрения временной сложности, даже если количество элементов в связанном списке значительно увеличивается.
4. Очередь
Очередь — это набор элементов, которые хранятся в линейной последовательности. Элементы можно добавлять только на одном конце последовательности, а элементы можно удалять только на другом конце последовательности.
По соглашению конец последовательности, в которой добавляются элементы, называется задней, хвостовой или задней частью очереди, а конец, в котором элементы удаляются, называется началом или началом очереди. Это в точности аналогично очередям, где люди выстраиваются в очередь, чтобы дождаться товаров или услуг.
Операция добавления элемента в конец очереди называется постановкой в очередь.
Операция удаления элемента с фронта называется удалением из очереди.
Другие операции также могут быть разрешены, часто включая операцию просмотра или переднюю операцию, которая возвращает значение следующего элемента, подлежащего удалению из очереди, не удаляя его из очереди.
Операции очереди делают ее структурой данных «первым пришел — первым обслужен» (FIFO). В структуре данных FIFO первый элемент, добавленный в очередь, будет первым удаленным.
Это эквивалентно требованию, что после добавления нового элемента все элементы, которые были добавлены ранее, должны быть удалены, прежде чем можно будет удалить новый элемент.
Код для создания очереди
Создайте класс с инициализированной пустой очередью (массив за сценой).
class SimpleQueue:
def __init__(self):
self.queue = []
Проверьте, пуста ли очередь или нет
def is_empty(self):
return self.queue == []
Теперь поставьте в очередь (добавьте элемент) в очередь
def enqueue(self, item):
self.queue.insert(0, item)
# 0 is the index of the element to insert
Найдите размер очереди
def size(self):
return len(self.queue)
Теперь из очереди (удалить элемент) в очередь
def dequeue(self):
return self.queue.pop()
Найдите размер очереди
def size(self):
return len(self.queue)
Все вместе с get_queue для просмотра содержимого очереди
class SimpleQueue:
def __init__(self):
self.items = []
def is_empty(self):
return self.items == []
def enqueue(self, item):
self.items.insert(0, item)
def dequeue(self):
return self.items.pop()
def size(self):
return len(self.items)
def get_queue(self):
return self.items
Теперь давайте проверим очередь
q = SimpleQueue()
q.enqueue(34)
q.enqueue("hi")
q.enqueue(4)
q.enqueue('dog')
q.enqueue(True)
q.enqueue(25)
print(q.size())
print(q.get_queue())
q.dequeue()
print(q.size())
print(q.get_queue())
q.dequeue()
print(q.get_queue())
Вывод приведенного выше кода
# Output 6 [25, True, 'dog', 4, 'hi', 34] 5 [25, True, 'dog', 4, 'hi'] [25, True, 'dog', 4]
Производительность очереди
Ниже приведены показатели производительности очереди в нотации Big O.
Производительность очереди с точки зрения временной сложности будет выглядеть следующим образом.
Доступ и поиск элементов в Queue будут масштабироваться линейно. Вставка и удаление элементов в очереди является постоянной с точки зрения временной сложности, даже если количество элементов в связанном списке значительно увеличивается.
Дерево
Древовидные структуры данных выглядят как древовидные структуры. Деревья иерархичны по своей природе.
Каждый узел в дереве может иметь одно из трех состояний.
- Это может быть родительский узел.
- Это может быть дочерний узел
- Он может быть и родителем, и ребенком одновременно.
Деревья очень хорошо знакомы нам в реальном мире, как будто мы рождаемся в генеалогическом древе с разветвленными предками и потомками.
Бинарные деревья — это особый тип древовидной структуры данных. Двоичные деревья начинаются с корневого узла, а затем могут содержать до двух дочерних узлов, левого и правого. Двоичное имя относится к тому, как дочерние узлы ограничены двумя узлами. Нет предела тому, насколько глубоко могут идти иерархические узлы дерева. Реальное преимущество использования бинарного дерева сводится к тому, как данные добавляются и сохраняются в дереве.
Добавление дерева основано на сравнениях, а не на сохранении баланса дерева. Поскольку данные дерева рассредоточены на основе сравнений, это делает добавление и поиск данных весьма эффективным. Несмотря на то, что всего элементов в этом дереве девять, требуется всего два шага ниже корня, чтобы найти 200, и один, чтобы найти 10. Сравните это с отсортированным списком, где вам нужно пройти весь путь до девятой позиции, чтобы найти 200. Из-за древовидной структуры это делает нотацию Big O логарифмической, что является одним из лучших показателей доступа, которые вы можете получить из структуры данных.
Операции с деревом
Теперь давайте посмотрим, как элементы добавляются в бинарное дерево.
Добавление первого элемента в бинарное дерево
Добавление элемента в существующее бинарное дерево
Поиск подходящего места для добавления нового элемента
Добавление еще одного элемента 100
Добавить еще один элемент 30
и это продолжается…
Однако за хорошую производительность приходится платить, поскольку кодирование двоичного дерева — одна из наиболее сложных структур данных.
Теперь давайте сначала напишем код для создания объекта node. Вы можете рассматривать этот объект как шаблон для создания узлов. Этот фрагмент кода может использоваться другими программами или функциями для создания и инициализации узлов.
Создайте объект Node, как показано ниже.
class Node(object):
def __init__(self, item):
self.item = item
self.left = None
self.right = None
self.parent = None
def get_item(self):
return self.item
def get_left(self):
return self.left
def set_left(self, item):
self.left = item
def get_right(self):
return self.right
def set_right(self, item):
self.right = item
def get_parent(self):
return self.parent
def set_parent(self, item):
self.parent = item
Теперь создайте двоичное дерево с пустым корнем и нулевым размером.
from DataStructures.Tree.node import Node
class BinaryTree(object):
def __init__(self):
self.root = None
self.size = 0
Добавьте функцию для определения размера дерева в любое время
def get_size(self):
return self.size
Добавить элемент
def add_item(self, item):
node = Node(item)
# If this is first item in the tree , set it as root
if self.root is None:
self.root = node
print('Root is empty. Setting root to : %s' % node.get_item())
self.size += 1
else: # Otherwise, we need to insert the item into the tree using the binary tree insert algorithm
self.insert(self.root, node)
def insert(self, parent, child):
# If child is less than parent, it goes here
if child.get_item() < parent.get_item():
if parent.get_left() is None: # If left node is None (null) we have found our spot!
parent.set_left(child)
child.set_parent(parent)
self.size += 1
# Otherwise we need to call insert again and test for left or right (recursion)
else:
self.insert(parent.get_left(), child)
# If child is greater than parent, it goes to the right
elif child.get_item() > parent.get_item():
# If right node is null, we have found our spot!
if parent.get_right() is None:
parent.set_right(child)
child.set_parent(parent)
self.size += 1
else:
# Otherwise we need to call insert again and test for left and right using recursion
self.insert(parent.get_right(), child)
# If the parent and child happen to be equal, we don't do anything assuming that the data in the binary tree is unique
Поиск элемента
def does_tree_contains(self, item):
current_node = self.get_node(item)
if current_node is None:
return False
else:
return True
def get_node(self, item):
current_node = self.root
while current_node is not None:
if item == current_node.get_item():
return current_node
elif item < current_node.get_item():
current_node = current_node.get_left()
else:
current_node = current_node.get_right()
return None
Удалить элемент
def delete_item(self, item):
deleted = False
# Make sure the root isn't null meaning the tree is empty
if self.root is None:
return False
if self.get_node(item) is None:
return False
# Find the node to delete
node_to_be_deleted = self.get_node(item)
print("Deleting node %s" % node_to_be_deleted.get_item())
if node_to_be_deleted is not None:
# If the node to delete doesn't have any children, just delete it
if node_to_be_deleted.get_left() is None and node_to_be_deleted.get_right() is None:
self.unlink_item(node_to_be_deleted, None)
deleted = True
# If the node to delete only has a right child, remove it in the h hierarchy
elif node_to_be_deleted.get_left() is None and node_to_be_deleted.get_right() is not None:
self.unlink_item(node_to_be_deleted, node_to_be_deleted.get_right())
deleted = True
# If the node to delete only has a left child, remove it in the h hierarchy
elif node_to_be_deleted.get_left() is not None and node_to_be_deleted.get_right() is None:
self.unlink_item(node_to_be_deleted, node_to_be_deleted.get_left())
deleted = True
# The node has both children, do a node swap to delete
else:
child = node_to_be_deleted.get_left()
while child.get_right() is not None and child.get_left() is not None:
child = child.get_right()
# We have the right most leaf node. We can replace the current node with this node
child.get_parent().set_right(None) # Remove the leaf node from it's current position
child.set_left(node_to_be_deleted.get_left())
child.set_right(node_to_be_deleted.get_right().get_right())
self.unlink_item(node_to_be_deleted, child)
deleted = True
if deleted:
self.size -= 1
return deleted
def unlink_item(self, node_to_be_deleted, new_node):
if node_to_be_deleted.get_item() == self.root.get_item():
new_node.set_left(node_to_be_deleted.get_left())
new_node.set_right(node_to_be_deleted.get_right())
self.root = new_node
elif node_to_be_deleted.get_parent().get_right().get_item() == node_to_be_deleted.get_item():
node_to_be_deleted.get_parent().set_right(new_node)
else:
node_to_be_deleted.get_parent().set_left(new_node)
Простая вспомогательная функция для отображения данных дерева
def display_tree_data(self):
print("Tree Root is: %s" % self.root.get_item())
child_node = self.root.get_left()
print("<< Left side Nodes from tree Root >>")
while child_node:
print("Left child_node is %s" % child_node.get_item())
if child_node.get_right() is not None:
print("Right child_node is %s" % child_node.get_right().get_item())
child_node = child_node.get_left()
print("<< Right side Nodes from tree Root >>")
child_node = self.root.get_right()
while child_node:
print("Right child_node is %s" % child_node.get_item())
if child_node.get_left() is not None:
print("Left child_node is %s" % child_node.get_left().get_item())
child_node = child_node.get_right()
Тестируем все вместе
bt = BinaryTree()
print(bt.get_size())
bt.add_item(50)
bt.add_item(25)
bt.add_item(100)
bt.add_item(150)
bt.add_item(200)
bt.add_item(10)
bt.add_item(30)
bt.add_item(15)
bt.add_item(110)
print("Does the Node Contains 400? : %s" % bt.does_tree_contains(400))
print("Does the Node Contains 25? : %s" % bt.does_tree_contains(25))
print("Does the Node Contains 0? : %s" % bt.does_tree_contains(0))
print("Does the Node Contains 10? : %s" % bt.does_tree_contains(10))
print("Tree size is: %s" % bt.get_size())
bt.display_tree_data()
print("Deleting 50 from the tree: %s" % bt.delete_item(50))
print("Tree size is: %s" % bt.get_size())
print("New Root is: " + str(bt.root.get_item()))
bt.display_tree_data()
print("Deleting 50 from the tree: " + str(bt.delete_item(50)))
bt.display_tree_data()
print("Deleting 200 from the tree: " + str(bt.delete_item(200)))
bt.display_tree_data()
print("Deleting 15 from the tree: " + str(bt.delete_item(15)))
bt.display_tree_data()
bt.add_item(40)
bt.add_item(113)
bt.display_tree_data()
print("Tree size is: %s" % bt.get_size())
Вывод приведенного выше кода
# Output 0 Root is empty. Setting root to : 50 Does the Node Contains 400? : False Does the Node Contains 25? : True Does the Node Contains 0? : False Does the Node Contains 10? : True Tree size is: 9 Tree Root is: 50 << Left side Nodes from tree Root >> Left child_node is 25 Right child_node is 30 Left child_node is 10 Right child_node is 15 << Right side Nodes from tree Root >> Right child_node is 100 Right child_node is 150 Left child_node is 110 Right child_node is 200 Deleting 50 from the tree: True Tree size is: 8 New Root is: 30 Tree Root is: 30 << Left side Nodes from tree Root >> Left child_node is 25 Left child_node is 10 Right child_node is 15 << Right side Nodes from tree Root >> Right child_node is 100 Right child_node is 150 Left child_node is 110 Right child_node is 200 Deleting 50 from the tree: False Tree Root is: 30 << Left side Nodes from tree Root >> Left child_node is 25 Left child_node is 10 Right child_node is 15 << Right side Nodes from tree Root >> Right child_node is 100 Right child_node is 150 Left child_node is 110 Right child_node is 200 Deleting 200 from the tree: True Tree Root is: 30 << Left side Nodes from tree Root >> Left child_node is 25 Left child_node is 10 Right child_node is 15 << Right side Nodes from tree Root >> Right child_node is 100 Right child_node is 150 Left child_node is 110 Deleting 15 from the tree: True Tree Root is: 30 << Left side Nodes from tree Root >> Left child_node is 25 Left child_node is 10 << Right side Nodes from tree Root >> Right child_node is 100 Right child_node is 150 Left child_node is 110 Tree Root is: 30 << Left side Nodes from tree Root >> Left child_node is 25 Left child_node is 10 << Right side Nodes from tree Root >> Right child_node is 100 Left child_node is 40 Right child_node is 150 Left child_node is 110 Tree size is: 8
Производительность бинарного дерева
Ниже приведены показатели производительности нотации Big O для двоичного дерева.
Производительность двоичного дерева с точки зрения временной сложности будет выглядеть следующим образом.
Как видите, все четыре операции в двоичном дереве имеют одинаковую производительность O(log n), что делает их отличным выбором для эффективного хранения, поиска, доступа и удаления данных.
Вывод
Мы увидели 5 основных структур данных, их реализацию и производительность с точки зрения нотации Bog O. Каждая из этих структур данных имеет свои сильные и слабые стороны. Как программисты, мы должны выбирать эти структуры данных в зависимости от проблемы, которую нам нужно решить. Во многих случаях достижение масштаба и производительности в информатике требует компромиссов. Поэтому выбирайте тот люкс, который лучше всего подходит для ваших условий.
Понимание этих основных концепций поможет вам писать лучшие программы. Освоение этих алгоритмов и структур данных также повысит вашу уверенность в технических дискуссиях и интервью.
Исходный код
Если вам интересно изучить исходные коды этой статьи, вы можете найти их в моем Git Hub: https://github.com/sachinsadasivan/algorithms-and-data-structures.
