Рубрики

Обзор структур данных | Набор 1 (линейные структуры данных)

Структура данных — это особый способ организации данных в компьютере, чтобы их можно было эффективно использовать. Идея состоит в том, чтобы уменьшить пространственно-временные сложности различных задач. Ниже приведен обзор некоторых популярных линейных структур данных.

1. Массив
2. Связанный список
3. Стек
4. Очередь

массив

Массив — это структура данных, используемая для хранения однородных элементов в смежных местах. Размер массива должен быть указан перед сохранением данных.

Let size of array be n.
Accessing Time: O(1) [This is possible because elements
                      are stored at contiguous locations]   
Search Time:   O(n) for Sequential Search: 
               O(log n) for Binary Search [If Array is sorted]
Insertion Time: O(n) [The worst case occurs when insertion 
                     happens at the Beginning of an array and 
                     requires shifting all of the elements]
Deletion Time: O(n) [The worst case occurs when deletion 
                     happens at the Beginning of an array and 
                     requires shifting all of the elements]

Пример: например, скажем, мы хотим хранить оценки всех учащихся в классе, мы можем использовать массив для их хранения. Это помогает сократить использование количества переменных, поскольку нам не нужно создавать отдельную переменную для отметок каждого предмета. Все метки могут быть доступны путем простого обхода массива.

Связанный список

Связанный список — это линейная структура данных (например, массивы), где каждый элемент является отдельным объектом. Каждый элемент (то есть узел) списка состоит из двух элементов — данных и ссылки на следующий узел.

Типы связанного списка:
1. Singlely Linked List: в этом типе связанного списка каждый узел хранит адрес или ссылку на следующий узел в списке, а последний узел имеет следующий адрес или ссылку как NULL. Например 1-> 2-> 3-> 4-> NULL

2. Вдвойне связанный список: в этом типе связанного списка есть две ссылки, связанные с каждым узлом, одна из ссылок указывает на следующий узел и одну на предыдущий узел. Преимущество этой структуры данных в том, что мы можем перемещаться в обоих направлениях, и для удаления нам не нужно иметь явный доступ к предыдущему узлу. Например. NULL23-> NULL

3. Круговой связанный список: Круговой связанный список — это связанный список, в котором все узлы соединены в круг. В конце нет NULL. Круговой связанный список может быть однократно круговым связанным списком или дважды круговым связанным списком. Преимущество этой структуры данных в том, что любой узел может быть сделан в качестве начального узла. Это полезно при реализации циклической очереди в связанном списке. Например. 1-> 2-> 3-> 1 [Следующий указатель последнего узла указывает на первый]

Accessing time of an element : O(n)
Search time of an element : O(n)
Insertion of an Element : O(1) [If we are at the position 
                                where we have to insert 
                                an element] 
Deletion of an Element : O(1) [If we know address of node
                               previous the node to be 
                               deleted] 

Пример: рассмотрим предыдущий пример, где мы сделали массив оценок ученика. Теперь, если новый предмет добавлен в курс, его оценки также будут добавлены в массив оценок. Но размер массива был фиксирован, и он уже заполнен, поэтому он не может добавлять новые элементы. Если мы сделаем массив размером больше, чем количество предметов, возможно, что большая часть массива останется пустой. Мы уменьшаем потери пространства. Связанный список формируется, который добавляет узел только тогда, когда вводится новый элемент. Вставки и удаления также становятся проще благодаря связанному списку.
Один большой недостаток связанного списка заключается в том, что произвольный доступ не разрешен. С массивами мы можем получить доступ к i-му элементу за O (1) раз. В связанном списке это занимает Θ (i) время.

стек

Стек или LIFO (последний пришел, первый вышел) — это абстрактный тип данных, который служит набором элементов с двумя основными операциями: push, который добавляет элемент в коллекцию, и pop, который удаляет последний добавленный элемент , В стеке обе операции push и pop выполняются на одном конце, который является вершиной стека. Это может быть реализовано с использованием как массива, так и связанного списка.

Insertion : O(1)
Deletion :  O(1)
Access Time : O(n) [Worst Case]
Insertion and Deletion are allowed on one end. 

Пример: стеки используются для поддержки вызовов функций (последняя вызванная функция должна завершить выполнение в первую очередь), мы всегда можем удалить рекурсию с помощью стеков. Стеки также используются в тех случаях, когда мы должны обратить слово, проверить сбалансированные скобки и в редакторах, где слово, которое вы ввели последним, удаляется первым при использовании операции отмены. Точно так же, чтобы реализовать обратно функциональность в веб-браузерах.

Очередь

Очередь или FIFO (сначала пришел, первым вышел) — это абстрактный тип данных, который служит коллекцией элементов с двумя основными операциями: постановка в очередь, процесс добавления элемента в коллекцию (элемент добавляется с задней стороны). ) и dequeue, процесс удаления первого добавленного элемента. (Элемент снят с лицевой стороны). Это может быть реализовано с использованием как массива, так и связанного списка.

Insertion : O(1)
Deletion  : O(1)
Access Time : O(n) [Worst Case]

Пример. Очередь, как следует из названия, — это структура данных, построенная в соответствии с очередями автобусной остановки или поезда, где человек, стоящий в очереди (стоящий дольше всего), первым получает билет. Таким образом, любая ситуация, когда ресурсы распределяются между несколькими пользователями и обслуживаются в порядке поступления. Примеры включают планирование ЦП, планирование диска. Другое применение очереди — когда данные передаются асинхронно (данные не обязательно принимаются с той же скоростью, что и отправленные) между двумя процессами. Примеры включают буферы ввода-вывода, каналы, файловый ввод-вывод и т. Д.

Циклическая очередь Преимущество этой структуры данных состоит в том, что она уменьшает потери пространства в случае реализации массива, поскольку вставка (n + 1) -го элемента выполняется по 0-му индексу, если он пуст.

Обзор структур данных | Набор 2 (двоичное дерево, BST, куча и хэш)

Эта статья предоставлена Абхираджем Смитом . Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Обзор структур данных | Набор 1 (линейные структуры данных)

0.00 (0%) 0 votes