Как написать свой linkedlist в java
Перейти к содержимому

Как написать свой linkedlist в java

  • автор:

Реализация методов в LinkedList

Всем добрый вечер. Прошу помощи в таком вопросе: у меня есть LinkedList с реализованными в нем методами, не получается реализовать 3 метода: public boolean remove(int index) — удаление элемента по индексу; public boolean removeElement(int element) — удаление самого элемента и public void set(int index, int element) — замена элемента. Помогите кто чем может, заранее благодарен.

package com.inguarus; public class IntLinkedList extends BaseList implements IntList < private Node first; private Node last; private static class Node < int element; Node next; Node previous; public Node(int element) < this.element = element; >> @Override public void add(int element) < Node newNode = new Node(element); if (first == null) < newNode.next = null; newNode.previous = null; first = newNode; last = newNode; >else < last.next = newNode; newNode.previous = last; last = newNode; >size++; > @Override public void add(int index, int element) < if (index < 0 || index >= size) < throw new IndexOutOfBoundsException(); >Node newNode = new Node(element); if (index == 0) < add(element); >if (index == size) < last.next = newNode; last = newNode; >Node oldNode = first; for (int i = 0; i < index; i++) < oldNode = oldNode.next; >Node oldPrevious = oldNode.previous; oldPrevious.next = newNode; oldNode.previous = newNode; newNode.previous = oldPrevious; newNode.next = oldNode; size++; > @Override public void clear() < first = null; last = null; size = 0; >@Override public boolean contains(int element) < for (int i = 0; i < size; i++) < if (get(i) == element) < return true; >> return false; > @Override public int get(int index) < if (index < 0 || index >= size) < throw new IndexOutOfBoundsException(); >Node result = first; for (int i = 0; i < index; i++) < result = result.next; >return result.element; > @Override public boolean isEmpty() < return size == 0; >@Override public boolean remove(int index) < if (index < 0 || index >= size) < throw new IllegalArgumentException(); >return false; > @Override public boolean removeElement(int element) < return false; >@Override public void set(int index, int element) < >> 

Отслеживать

23.4k 3 3 золотых знака 50 50 серебряных знаков 70 70 бронзовых знаков

задан 8 июн 2018 в 15:14

85 1 1 серебряный знак 8 8 бронзовых знаков

1 ответ 1

Сортировка: Сброс на вариант по умолчанию

Реализовал нужные мне методы с помощью дополнительных методов:

public boolean remove(int index) < if (index < 0 || index >size - 1) < throw new IllegalArgumentException(); >if (index == 0) < first = first.next; >else < Node node = findNodeBeforeByIndex(index); Node tmp = findByIndex(index); node.next = tmp.next; >size--; return false; > public boolean removeElement(int element) < if (size == 0) < return false; >else if (size == 1) < first = null; last = null; size = 0; return true; >Node nodeBefore = findNodeBefore(element); if (nodeBefore.element == 0) < first = first.next; size--; return true; >else if (nodeBefore != null) < if (last.element == element) < nodeBefore.next = null; last = nodeBefore; >else < nodeBefore.next = nodeBefore.next.next; >size--; return true; > return false; > private Node findByIndex(int index) < if (index < 0 || index >size - 1) < throw new IndexOutOfBoundsException(); >int tmpIndex = 0; if (first == null) < throw new IndexOutOfBoundsException(); >if (index == 0) < return first; >Node node = first; while (node.next != null) < node = node.next; tmpIndex++; if (tmpIndex == index) < return node; >> throw new IndexOutOfBoundsException(); > private Node findNodeBefore(int value) < if (first.element == value) < return new Node(); >Node node = first; while (node.next != null) < if (node.next.element == value) < return node; >node = node.next; > return null; > private Node findNodeBeforeByIndex(int index) < if (index size - 1) < return null; >int count = 0; Node node = first; while (node.next != null) < if (count == index - 1) < return node; >count++; node = node.next; > return null; > 

#2 — Коллекции данных ArrayList и LinkedList

#2 - Коллекции данных ArrayList и LinkedList

Java обладает множеством коллекций, что позволяют хранить наборы данных или другими словами массивы данных. За урок будут рассмотрены такие коллекции как ArrayList и LinkedList.

Видеоурок

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

Коллекции в языке Java

Стандартные массивы предоставляют лишь небольшой функционал по работе с элементами. Если мы захотим добавить 10 элемент в массив что состоит из 9 элементов, то будет выдана ошибка. Такой подход совсем неудобен, ведь не позволяет динамично управлять данными в массиве.

На помощь приходят коллекции данных. В языке Java есть множество интерфейсов по работе с коллекциями. Все такие интерфейсы представлены ниже:

Как видно из фото, каждая коллекция представляет из себя именно интерфейс, а не класс. Основным интерфейсом является Collection.

Вы можете создать коллекцию (другими словами: массив данных) на основе Collection или же на основе других интерфейсов, что являются наследниками интерфейса Collection.

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

Основные коллекции

Помимо главного интерфейса Collection есть три других главных формата:

  • List — коллекция для создания массивов данных, где индексами являются числа (0, 1, 2 и так далее);
  • Set — тоже самое что List, вот только в Set нельзя установить повторяющиеся элементы;
  • Map — коллекция для создания массивов данных, где индексами являются ключи («one», «2», «three» и так далее).

У каждого интерфейса есть интерфейсы наследники, что дополняют функциями базовый интерфейс. К примеру, можно создать коллекцию на основе класса List, а можно расширить её функционал за счёт создания коллекции на основе LinkedList.

Создание коллекций на основе разных интерфейсов очень схоже, поэтому в видео уроке были рассмотрены лишь ArrayList и LinkedList.

Коллекции безусловно удобнее чем массивы данных. Тем не менее, не стоит злоупотреблять ими, так как они занимают больше оперативной памяти, что может повлиять на скорость загрузки приложения в целом.

Работа с коллекциями

Для работы с коллекциями необходимо подключить соответсвующие интерфейсы из java.util .

При создании коллекции необходимо указать тип данных, имя, а также выделение памяти:

ArrayList numbers = new ArrayList<>(1); LinkedList names = new LinkedList<>();

Для работы с элементами существует множество методов. Наиболее часто используемые представлены ниже:

  • add() — добавление элемента в конец массива;
  • remove() — удаление элемента из массива по его индексу;
  • clear() — очистка всего массива;
  • size() — получение размера массива (количество элементов);
  • addFirst() — добавление элемента в начало массива;
  • addLast() — добавление элемента в конец;
  • clone() — выполняет клонирование массива;
  • get() — возвращает элемент по индексу;
  • getFirst() — возвращает первый элемент в массиве;
  • getLast() — возвращает последний элемент в массиве;
  • set(index, element) — меняет значение элемента по индексу.
Весь код будет доступен после подписки на проект!

Как написать свой linkedlist в java

Обобщенный класс LinkedList представляет структуру данных в виде связанного списка. Он наследуется от класса AbstractSequentialList и реализует интерфейсы List, Dequeue и Queue . То есть он соединяет функциональность работы со списком и фукциональность очереди.

Класс LinkedList имеет следующие конструкторы:

  • LinkedList() : создает пустой список
  • LinkedList(Collection col) : создает список, в который добавляет все элементы коллекции col

LinkedList содержит все те методы, которые определены в интерфейсах List, Queue, Deque. Некоторые из них:

  • addFirst() / offerFirst() : добавляет элемент в начало списка
  • addLast() / offerLast() : добавляет элемент в конец списка
  • removeFirst() / pollFirst() : удаляет первый элемент из начала списка
  • removeLast() / pollLast() : удаляет последний элемент из конца списка
  • getFirst() / peekFirst() : получает первый элемент
  • getLast() / peekLast() : получает последний элемент

Рассмотрим применение связанного списка:

import java.util.LinkedList; public class Program < public static void main(String[] args) < LinkedListstates = new LinkedList(); // добавим в список ряд элементов states.add("Germany"); states.add("France"); states.addLast("Great Britain"); // добавляем на последнее место states.addFirst("Spain"); // добавляем на первое место states.add(1, "Italy"); // добавляем элемент по индексу 1 System.out.printf("List has %d elements \n", states.size()); System.out.println(states.get(1)); states.set(1, "Portugal"); for(String state : states) < System.out.println(state); >// проверка на наличие элемента в списке if(states.contains("Germany")) < System.out.println("List contains Germany"); >states.remove("Germany"); states.removeFirst(); // удаление первого элемента states.removeLast(); // удаление последнего элемента LinkedList people = new LinkedList(); people.add(new Person("Mike")); people.addFirst(new Person("Tom")); people.addLast(new Person("Nick")); people.remove(1); // удаление второго элемента for(Person p : people) < System.out.println(p.getName()); >Person first = people.getFirst(); System.out.println(first.getName()); // вывод первого элемента > > class Person < private String name; public Person(String value)< name=value; >String getName() >

Здесь создаются и используются два списка: для строк и для объектов класса Person. При этом в дополнение к методам addFirst/removeLast и т.д., нам также доступны стандартные методы, определенные в интерфейсе Collection: add() , remove , contains , size и другие. Поэтому мы можем использовать разные методы для одного и того же действия. Например, добавление в самое начало списка можно сделать так: states.addFirst(«Spain»); , а можно сделать так: states.add(0, «Spain»);

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

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

Этот же автор описывает принципы работы LinkedList, однако часть данных устарела еще с выходом Java 7, поэтому попытка детально разобраться, что происходит внутри этой коллекции, по рисункам tarzan82 уже сложно. Да и в других источниках я не встретила понятных картинок, потому и возникла идея написать эту статью.

Итак, LinkedList — класс, реализующий два интерфейса — List и Deque. Это обеспечивает возможность создания двунаправленной очереди из любых (в том числе и null) элементов. Каждый объект, помещенный в связанный список, является узлом (нодом). Каждый узел содержит элемент, ссылку на предыдущий и следующий узел. Фактически связанный список состоит из последовательности узлов, каждый из которых предназначен для хранения объекта определенного при создании типа.

Разберемся, что же происходит, когда мы пишем уже простые и привычные строки кода.

1. Создание связанного списка

LinkedList numbers = new LinkedList<>();

Данный код создает объект класса LinkedList и сохраняет его в ссылке numbers. Созданный объект предназначен для хранения целых чисел (Integer). Пока этот объект пуст.

Класс LinkedList содержит три поля:

// модификатор transient указывает на то, что данное свойство класса нельзя // сериализировать transient int size = 0; transient Node first; transient Node last;

2. Добавление объекта в конец связанного списка

numbers.add(8);

Данный код добавляет число 8 в конец ранее созданного списка. Под «капотом» этот метод вызывает ряд других методов, обеспечивающих создание объекта типа Integer, создание нового узла, установку объекта класса Integer в поле item этого узла, добавление узла в конец списка и установку ссылок на соседние узлы.

Для установки ссылок на предыдущий и следующий элементы LinkedList использует объекты своего вложенного класса Node:

private static class Node  < E item; Nodenext; Node prev; Node(Node prev, E element, Node next) < this.item = element; this.next = next; this.prev = prev; >>

При каждом добавлении объекта в список создается один новый узел, а также изменяются значения полей связанного списка (size, first, last).

В случае с добавлением первого элемента создается узел, у которого предыдущий и следующий элементы отсутствуют, т.е. являются null, размер коллекции увеличивается на 1, а созданный узел устанавливается как первый и последний элемент коллекции.

Добавим еще один элемент в нашу коллекцию:

numbers.add(5);

Сначала создается узел для нового элемента (число 5) и устанавливается ссылка на существующий элемент (узел с числом 8) коллекции как на предыдущий, а следующим элементом у созданного узла остается null. Также этот новый узел сохраняется в переменную связанного списка last:

Как можно увидеть на рис. 4, первый элемент коллекции (под индексом 0) пока ссылается на null как на следующий элемент. Теперь эта ссылка заменяется и первый элемент начинает ссылаться на второй элемент коллекции (под индексом 1), а также увеличивается размер коллекции:

3. Добавление объекта в середину связанного списка

numbers.add(1, 13);

LinkedList позволяет добавить элемент в середину списка. Для этого используется метод add(index, element), где index — это место в списке, куда будет вставлен элемент element.

Как и метод add(element), данный метод вызывает несколько других методов. Сначала осуществляется проверка значения index, которое должно быть положительным числом, меньшим или равным размеру списка. Если index не удовлетворит этим условиям, то будет сгенирировано исключение IndexOutOfBoundsException.

Затем, если index равен размеру коллеции, то осуществляются действия, описанные в п. 2, так как фактически необходимо вставить элемент в конец существующего списка.

Если же index не равен size списка, то осуществляется вставка перед элементом, который до этой вставки имеет заданный индекс, т.е. в данном случае перед узлом со значением 5.

Для начала с помощью метода node(index) определяется узел, находящийся в данный момент под индексом, под который нам необходимо вставить новый узел. Поиск данного узла осуществляется с помощью простого цикла for по половине списка (в зависимости от значения индекса — либо с начала до элемента, либо с конца до элемента). Далее создается узел для нового элемента (число 13), ссылка на предыдущий элемент устанавливается на узел, в котором элементом является число 8, а ссылка на следующий элемент устанавливается на узел, в котором элементом является число 5. Ссылки ранее существующих узлов пока не изменены:

Теперь последовательно заменяются ссылки: для элемента, следующего за новым элементом, заменяется ссылка на предыдущий элемент (теперь она указывает на узел со значением 13), для предшествующего новому элементу заменяется ссылка на следующий элемент (теперь она указывает на узел со значением 5). И в последнюю очередь увеличивается размер списка:

4. Удаление объекта из списка

Для удаления одного элемента из списка класс LinkedList предлагает нам аж 10 методов, различающихся по типу возвращаемого значения, наличию или отсутствию выбрасываемых исключений, а также способу указания, какой именно элемент следует удалить:

Рассмотрим удаление элемента из связанного списка по его значению. Удалим элемент со значением 5 из нижепредставленного списка:

numbers.remove(Integer.valueOf(5));

Обратите внимание, что принимаемым значением в методе remove(object) является именно объект, если же мы попытаемся удалить элемент со значением 5 следующей строкой

numbers.remove(5);

то получим IndexOutOfBoundsException, т.к. компиллятор воспримет число 5 как индекс и вызовет метод remove(index).

Итак, что же происходит при вызове метода remove(object)? Сначала искомый объект сравнивается по порядку со всеми элементами, сохраненными в узлах списка, начиная с нулевого узла. Когда найден узел, элемент которого равен искомому объекту, первым делом элемент сохраняется в отдельной переменной. Потом переопределяются ссылки соседних узлов так, чтобы они указывали друг на друга:

Затем обнуляется значение узла, который содержит удаляемый объект, а также уменьшается размер коллекции:

Теперь вернемся к тому моменту, что элемент из удаляемого узла мы сохраняли в памяти. Зачем мы это делали, спросите вы, если эти данные мы нигде дальше не использовали. Дело в том, что рассматриваемый нами метод в результате своей работу не возвращает удаленный элемент, потому данные, возврещенные вызванным в рамках работы метода unlink(node), вызванного методом remove(object), просто не понадобились. А вот когда мы используем метод remove(index), также вызывающий метод unlink(node), то значение данного элемента последовательно возвращается сначала методом unlink(node), а затем и методом remove(index). Похожая ситуация наблюдается и в остальных методах, возвращающих значение удаленного элемента, только внутри вызываются другие методы, отсоединяющие ссылку: в методах poll(), pollFirst(), remove() и removeFirst() это метод unlinkFirst(node), а в методах pollLast() и removeLast() — метод unlinkLast(node).

Итак, что следует помнить о LinkedList, решая, использовать ли данную коллекцию:

  • не синхронизирована;
  • позволяет хранить любые объекты, в том числе null и повторяющиеся;
  • за константное время O(1) выполняются операции вставки и удаления первого и последнего элемента, операции вставки и удаления элемента из середины списка (не учитывая время поиска позиции элемента, который осуществляется за линейное время);
  • за линейное время O(n) выполняются операции поиска элемента по индексу и по значению.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *