Как написать свой 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 золотых знака 49 49 серебряных знаков 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; > 

Как написать свой 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»);

31.8. Java – Класс LinkedList

Класс LinkedList в Java расширяет AbstractSequentialList и реализует интерфейс List. Он предоставляет структуру данных связанных списков.

Конструкторы

Ниже приведены конструкторы, поддерживаемые классом LinkedList.

№	Конструктор и описание
1	LinkedList( ) Этот конструктор создает пустой связанный список.
2	LinkedList(Collection c) Этот конструктор создает связанный список, который инициализируется элементами коллекции c.

Методы

Помимо применения методов, унаследованных от родительских классов, LinkedList определяет следующие методы:

№	и описание
1	void add(int index, Object element) Вставляет указанный элемент в указанный указатель позиции в этом списке. Вызывает IndexOutOfBoundsException, если указанный индекс выходит за допустимые пределы (index size()).
2	boolean add(Object o) Добавляет указанный элемент в конец этого списка.
3	boolean addAll(Collection c) Добавляет все элементы в указанной коллекции в конец этого списка в том порядке, в котором они возвращаются итератором указанной коллекции. Выбрасывает NullPointerException, если указанная коллекция имеет значение null (нуль).
4	boolean addAll(int index, Collection c) Вставляет все элементы указанной коллекции в этот список, начиная с указанной позиции. Вызывает NullPointerException, если указанная коллекция имеет значение null (нуль).
5	void addFirst(Object o) Вставляет данный элемент в начало этого списка.
6	void addLast(Object o) Добавляет данный элемент в конец этого списка.
7	void clear() Удаляет все элементы из этого списка.
8	Object clone() Возвращает мелкую копию этого LinkedList.
9	boolean contains(Object o) Возвращает true, если этот список содержит указанный элемент. Если точнее, то возвращает true тогда и только тогда, когда этот список содержит хотя бы один элемент e такой, что (o==null ? e==null : o.equals(e)).
10	Object get(int index) Возвращает элемент в указанной позиции в этом списке. Вызывает IndexOutOfBoundsException, если указанный индекс выходит за допустимые пределы (index = size()).
11	Object getFirst() Возвращает первый элемент в этом списке. Вызывает исключение NoSuchElementException, если этот список пуст.
12	Object getLast() Возвращает последний элемент в этом списке. Вызывает исключение NoSuchElementException, если этот список пуст.
13	int indexOf(Object o) Возвращает индекс в этом списке первого упоминания указанного элемента или -1, если список не содержит этот элемент.
14	int lastIndexOf(Object o) Возвращает индекс в этом списке последнего упоминания указанного элемента или -1, если список не содержит этот элемент.
15	ListIterator listIterator(int index) Возвращает список-итератор элементов в этом списке (в правильной последовательности), начиная с указанной позиции в списке. Вызывает IndexOutOfBoundsException, если указанный индекс выходит за пределы диапазона (index = size()).
16	Object remove(int index) Удаляет элемент в указанной позиции в этом списке. Вызывает исключение NoSuchElementException, если этот список пуст.
17	boolean remove(Object o) Удаляет первое упоминание указанного элемента в этом списке. Вызывает исключение NoSuchElementException, если этот список пуст. Вызывает IndexOutOfBoundsException, если указанный индекс выходит за пределы диапазона (index = size()).
18	Object removeFirst() Удаляет и возвращает первый элемент из этого списка. Выбрасывает исключение NoSuchElementException, если этот список пуст.
19	Object removeLast() Удаляет и возвращает последний элемент из этого списка. Вызывает исключение NoSuchElementException, если этот список пуст.
20	Object set(int index, Object element) Заменяет элемент в указанной позиции в этом списке указанным элементом. Вызывает IndexOutOfBoundsException, если указанный индекс выходит за пределы диапазона (index = size()).
21	int size() Возвращает количество элементов в этом списке.
22	Object[] toArray() Возвращает массив, содержащий все элементы в этом списке в правильном порядке. Выбрасывает NullPointerException, если указанный массив равен null (нулю).
23	Object[] toArray(Object[] a) Возвращает массив, содержащий все элементы в этом списке в правильном порядке; тип выполнения возвращаемого массива — тип указанного массива.

Пример

Следующая программа показывает реализацию некоторых методов, поддерживаемые LinkedList в Java:

import java.util.*; public class LinkedListDemo < public static void main(String args[]) < // Создаём LinkedList LinkedList ll = new LinkedList(); // Добавляем элементы в LinkedList ll.add("F"); ll.add("B"); ll.add("D"); ll.add("E"); ll.add("C"); ll.addLast("Z"); ll.addFirst("A"); ll.add(1, "A2"); System.out.println("Изначальное содержание ll: " + ll); // Удаляем элементы из LinkedList ll.remove("F"); ll.remove(2); System.out.println("Содержание ll после удаления: " + ll); // Удаляем первый и последний элементы ll.removeFirst(); ll.removeLast(); System.out.println("ll после удаления первого и последнего: " + ll); // Получаем и устанавливаем значение Object val = ll.get(2); ll.set(2, (String) val + " Изменено"); System.out.println("ll после изменения: " + ll); >> 

Получим следующий результат:

Изначальное содержание ll: [A, A2, F, B, D, E, C, Z] Содержание ll после удаления: [A, A2, D, E, C, Z] ll после удаления первого и последнего: [A2, D, E, C] ll после изменения: [A2, D, E Изменено, C] 

Оглавление

• 1. Java – Самоучитель для начинающих
• 2. Java – Обзор языка
• 3. Java – Установка и настройка
• 4. Java – Синтаксис
• 5. Java – Классы и объекты
• 6. Java – Конструкторы
• 7. Java – Типы данных и литералы
• 8. Java – Типы переменных
• 9. Java – Модификаторы
• 10. Java – Операторы
• 11. Java – Циклы и операторы цикла
• 11.1. Java – Цикл while
• 11.2. Java – Цикл for
• 11.3. Java – Улучшенный цикл for
• 11.4. Java – Цикл do..while
• 11.5. Java – Оператор break
• 11.6. Java – Оператор continue
• 12. Java – Операторы принятия решений
• 12.1. Java – Оператор if
• 12.2. Java – Оператор if..else
• 12.3. Java – Вложенный оператор if
• 12.4. Java – Оператор switch..case
• 12.5. Java – Условный оператор (? 🙂
• 13. Java – Числа
• 13.1. Java – Методы byteValue(), shortValue(), intValue(), longValue(), floatValue(), doubleValue()
• 13.2. Java – Метод compareTo()
• 13.3. Java – Метод equals()
• 13.4. Java – Метод valueOf()
• 13.5. Java – Метод toString()
• 13.6. Java – Метод parseInt()
• 13.7. Java – Метод Math.abs()
• 13.8. Java – Метод Math.ceil()
• 13.9. Java – Метод Math.floor()
• 13.10. Java – Метод Math.rint()
• 13.11. Java – Метод Math.round()
• 13.12. Java – Метод Math.min()
• 13.13. Java – Метод Math.max()
• 13.14. Java – Метод Math.exp()
• 13.15. Java – Метод Math.log()
• 13.16. Java – Метод Math.pow()
• 13.17. Java – Метод Math.sqrt()
• 13.18. Java – Метод Math.sin()
• 13.19. Java – Метод Math.cos()
• 13.20. Java – Метод Math.tan()
• 13.21. Java – Метод Math.asin()
• 13.22. Java – Метод Math.acos()
• 13.23. Java – Метод Math.atan()
• 13.24. Java – Метод Math.atan2()
• 13.25. Java – Метод Math.toDegrees()
• 13.26. Java – Метод Math.toRadians()
• 13.27. Java – Метод Math.random()
• 14. Java – Символы
• 14.1. Java – Метод Character.isLetter()
• 14.2. Java – Метод Character.isDigit()
• 14.3. Java – Метод Character.isWhitespace()
• 14.4. Java – Метод Character.isUpperCase()
• 14.5. Java – Метод Character.isLowerCase()
• 14.6. Java – Метод Character.toUpperCase()
• 14.7. Java – Метод Character.toLowerCase()
• 14.8. Java – Метод Character.toString()
• 15. Java – Строки
• 15.1. Java – Метод charAt()
• 15.2. Java – Метод compareTo()
• 15.3. Java – Метод compareToIgnoreCase()
• 15.4. Java – Метод concat()
• 15.5. Java – Метод contentEquals()
• 15.6. Java – Метод copyValueOf()
• 15.7. Java – Метод endsWith()
• 15.8. Java – Метод equals()
• 15.9. Java – Метод equalsIgnoreCase()
• 15.10. Java – Метод getBytes()
• 15.11. Java – Метод getChars()
• 15.12. Java – Метод hashCode()
• 15.13. Java – Метод indexOf()
• 15.14. Java – Метод intern()
• 15.15. Java – Метод lastIndexOf()
• 15.16. Java – Метод length()
• 15.17. Java – Метод matches()
• 15.18. Java – Метод regionMatches()
• 15.19. Java – Метод replace()
• 15.20. Java – Метод replaceAll()
• 15.21. Java – Метод replaceFirst()
• 15.22. Java – Метод split()
• 15.23. Java – Метод startsWith()
• 15.24. Java – Метод subSequence()
• 15.25. Java – Метод substring()
• 15.26. Java – Метод toCharArray()
• 15.27. Java – Метод toLowerCase()
• 15.28. Java – Метод toString()
• 15.29. Java – Метод toUpperCase()
• 15.30. Java – Метод trim()
• 15.31. Java – Метод valueOf()
• 15.32. Java – Классы StringBuilder и StringBuffer
• 15.32.1. Java – Метод append()
• 15.32.2. Java – Метод reverse()
• 15.32.3. Java – Метод delete()
• 15.32.4. Java – Метод insert()
• 15.32.5. Java – Метод replace()
• 16. Java – Массивы
• 17. Java – Дата и время
• 18. Java – Регулярные выражения
• 19. Java – Методы
• 20. Java – Потоки ввода/вывода, файлы и каталоги
• 20.1. Java – Класс ByteArrayInputStream
• 20.2. Java – Класс DataInputStream
• 20.3. Java – Класс ByteArrayOutputStream
• 20.4. Java – Класс DataOutputStream
• 20.5. Java – Класс File
• 20.6. Java – Класс FileReader
• 20.7. Java – Класс FileWriter
• 21. Java – Исключения
• 21.1. Java – Встроенные исключения
• 22. Java – Вложенные и внутренние классы
• 23. Java – Наследование
• 24. Java – Переопределение
• 25. Java – Полиморфизм
• 26. Java – Абстракция
• 27. Java – Инкапсуляция
• 28. Java – Интерфейсы
• 29. Java – Пакеты
• 30. Java – Структуры данных
• 30.1. Java – Интерфейс Enumeration
• 30.2. Java – Класс BitSet
• 30.3. Java – Класс Vector
• 30.4. Java – Класс Stack
• 30.5. Java – Класс Dictionary
• 30.6. Java – Класс Hashtable
• 30.7. Java – Класс Properties
• 31. Java – Коллекции
• 31.1. Java – Интерфейс Collection
• 31.2. Java – Интерфейс List
• 31.3. Java – Интерфейс Set
• 31.4. Java – Интерфейс SortedSet
• 31.5. Java – Интерфейс Map
• 31.6. Java – Интерфейс Map.Entry
• 31.7. Java – Интерфейс SortedMap
• 31.8. Java – Класс LinkedList
• 31.9. Java – Класс ArrayList
• 31.10. Java – Класс HashSet
• 31.11. Java – Класс LinkedHashSet
• 31.12. Java – Класс TreeSet
• 31.13. Java – Класс HashMap
• 31.14. Java – Класс TreeMap
• 31.15. Java – Класс WeakHashMap
• 31.16. Java – Класс LinkedHashMap
• 31.17. Java – Класс IdentityHashMap
• 31.18. Java – Алгоритмы Collection
• 31.19. Java – Iterator и ListIterator
• 31.20. Java – Comparator
• 32. Java – Дженерики
• 33. Java – Сериализация
• 34. Java – Сеть
• 34.1. Java – Обработка URL
• 35. Java – Отправка Email
• 36. Java – Многопоточность
• 36.1. Java – Синхронизация потоков
• 36.2. Java – Межпоточная связь
• 36.3. Java – Взаимная блокировка потоков
• 36.4. Java – Управление потоками
• 37. Java – Основы работы с апплетами
• 38. Java – Javadoc

#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) — меняет значение элемента по индексу.

Весь код будет доступен после подписки на проект!