Pull to refresh
  • by relevance
  • by date
  • by rating

Структуры данных в картинках. LinkedList

Java *
Приветствую вас, хабражители!

Продолжаю начатое, а именно, пытаюсь рассказать (с применением визуальных образов) о том как реализованы некоторые структуры данных в Java.



В прошлый раз мы говорили об ArrayList, сегодня присматриваемся к LinkedList.

LinkedList — реализует интерфейс List. Является представителем двунаправленного списка, где каждый элемент структуры содержит указатели на предыдущий и следующий элементы. Итератор поддерживает обход в обе стороны. Реализует методы получения, удаления и вставки в начало, середину и конец списка. Позволяет добавлять любые элементы в том числе и null.

Прочитать чуть больше
Total votes 50: ↑46 and ↓4 +42
Views 468K
Comments 22

Сравнение скорости работы ArrayList и LinkedList на практике

Java *
Sandbox
Приветствую Вас!

ArrayList и LinkedList — знают все. В каких ситуациях работает быстро, а в какой ситуации работает медленной тот или другой список — знают тоже все, кто в теории, а кто на практике. Данный пост подходит для тех, кто только начинает изучать Java, или кто слышал, о том «что быстрее», но не видел на практике.
Читать дальше →
Total votes 38: ↑13 and ↓25 -12
Views 51K
Comments 55

Вставка в середину: ArrayList против LinkedList

Programming *Java *Algorithms *
Как-то на собеседовании мне задали вопрос: какая реализация списка выполнит вставку в середину быстрее: ArrayList или LinkedList? С первого взгляда вопрос простой — нужно посчитать алгоритмическую сложность каждого варианта и сравнить их.
Читать дальше →
Total votes 42: ↑31 and ↓11 +20
Views 65K
Comments 116

Что «под капотом» у LinkedList?

Programming *Java *
Sandbox
Добрый день, хабрачитатели!

Как работает ArrayList, вполне понятно. Есть много статей по этому поводу, часть из них иллюстрированы замечательными картинками, так что даже новичкам становится сразу все ясно. К лучшим статьям на эту тему я отношу «Структуры данных в картинках. ArrayList», написанную tarzan82.

Этот же автор описывает принципы работы LinkedList, однако часть данных устарела еще с выходом Java 7, поэтому попытка детально разобраться, что происходит внутри этой коллекции, по рисункам tarzan82 уже сложно. Да и в других источниках я не встретила понятных картинок, потому и возникла идея написать эту статью.
Читать дальше →
Total votes 22: ↑16 and ↓6 +10
Views 84K
Comments 45

Связный список на Python: Коты в коробках

OTUS corporate blog Python *Programming *
И снова здравствуйте! В преддверии старта курса «Разработчик Python» подготовили для вас небольшой авторский материал о связных списках на Python.



Python очень удобный и многогранный язык, но по умолчанию не имеет такой структуры данных как связный список или LinkedList. Сегодня я поделюсь своими наработками на эту тему и расскажу немного о том, что из себя представляет эта структура данных. Эта статья будет интересна тем, кто впервые сталкивается с темой связных списков и хочет понять, как они работают с алгоритмической точки зрения.


Читать дальше →
Total votes 22: ↑16 and ↓6 +10
Views 34K
Comments 15

Hi Programming Language: linked list

Programming *Learning languages
Продолжаем конструировать язык Hi. Сегодня рассмотрим встроенную реализацию связного списка (linked list).

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

Не все промышленные языки имеют встроенную поддержку связного списка как структуры данных. Впрочем, его нетрудно реализовать самостоятельно как класс или структуру. Для комфортной работы с релевантными алгоритмами мы добавим встроенные двунаправленные связные списки уже в базовое определение языка Hi.

Для начала создадим экземпляр нашего экспериментального списка:

VAR list = <"I", "will", "be">
Читать дальше →
Total votes 8: ↑3 and ↓5 -2
Views 1.4K
Comments 47

Linked List: Когда нужно писать свой Copy-on-write в iOS?

Algorithms *Swift *
Sandbox

Я всегда думал: "А зачем нужно писать свой copy-on-write? Ведь круто, когда есть структуры и они такие быстрые, что всё делают за тебя."

Но все это не нужно, пока не начинаешь писать свои типы и не подсаживаешься на LinkedList'ы.

Что такое этот связанный список и какие у него преимущества?

Читать далее
Total votes 10: ↑7 and ↓3 +4
Views 4.8K
Comments 9

Алгоритм. Очередь с приоритетом

C++ *Algorithms *C *

В этой статье я покажу очередь с приоритетом с использованием linked list. Алгоритм простой и позволяет получить приоритетные сообщения раньше, чем остальные сообщения.

Я сначала поискал в интернете реализацию такого алгоритма. Первое, что я нашел, это решение на c++ с обычными массивами. То есть создается шаблонный класс и в нем создается два массива, один для чисел, другой для приоритетности. Мне показалось, что решение не очень хорошее, потому что при добавлении нового числа, создается новый массив и из старого копируются данные в новый массив. Чем больше очередь, тем больше копирования каждый раз. Ещё проблема при использовании массива - это что нельзя использовать в другом потоке очередь, пока ты не выполнишь полностью функцию вставки данных в очередь, так как смениться указатель на массив и так далее.

Алгоритм - очередь с приоритетом достаточно простой, мы создаем структуру, я опять буду показывать пример кода на C, и входящие данные будут числа. итак.

Читать далее
Total votes 17: ↑6 and ↓11 -5
Views 6K
Comments 14