У цьому блозі ми глибше розглянемо одну з найосновніших структур даних у комп'ютерних науках: зв'язаний список. Зокрема, ми зосередимося на реалізації однозв'язного списку в Java, розглянемо його методи та зрозуміємо складності часу і простору.
Що таке зв'язаний список?
Зв'язаний список — це лінійна структура даних, де елементи, відомі як вузли, з'єднані за допомогою вказівників. Кожен вузол містить дані та посилання (або ланку) на наступний вузол у послідовності.
Чому використовувати зв'язаний список?
Зв'язані списки мають перевагу над масивами в деяких ситуаціях, оскільки:
- Вони забезпечують гнучкість розміру.
- Вони ефективні при додаванні або видаленні елементів.
Деталі реалізації
Розглянемо реалізацію однозв'язного списку в Java:
Клас Node (Вузол)
Зв'язаний список побудований з вузлів, де кожен вузол містить:
value(дані, які ми зберігаємо у вузлі)next(вказівник, що посилається на наступний вузол у списку)
class Node {
int value;
Node next;
Node(int value) {
this.value = value;
}
}
Конструктор LinkedList
Щоб ініціалізувати новий зв'язаний список, ми створюємо конструктор, який встановлює голову, хвіст і довжину списку.
public LinkedList(int value) {
Node newNode = new Node(value);
head = newNode;
tail = newNode;
length = 1;
}
- Пояснення: Цей конструктор ініціалізує список з одним вузлом і встановлює як голову, так і хвіст на новий вузол.
Методи в LinkedList
Тепер давайте розглянемо методи, які керують нашим зв'язаним списком.
1. printList()
public void printList() {
Node temp = head;
while (temp != null) {
System.out.println(temp.value);
temp = temp.next;
}
}
Пояснення: Цей метод проходить через зв'язаний список, починаючи з голови, і виводить значення кожного вузла. Він зупиняється, коли досягає кінця (коли temp стає null).
2. getHead()
public void getHead() {
System.out.println("Head: " + head.value);
}
Пояснення: Цей метод виводить значення головного вузла. Голова — це перший вузол у списку.
3. getTail()
public void getTail() {
System.out.println("Tail: " + tail.value);
}
Пояснення: Цей метод виводить значення хвостового вузла. Хвіст — це останній вузол у списку.
4. getLength()
public void getLength() {
System.out.println("Length: " + length);
}
Пояснення: Цей метод виводить поточну кількість вузлів у зв'язаному списку, що зберігається в змінній length.
5. append(int value)
public void append(int value) {
Node newNode = new Node(value);
if (length == 0) {
head = newNode;
} else {
tail.next = newNode;
}
tail = newNode;
length++;
}
Пояснення: Цей метод додає новий вузол з заданим значенням value до кінця (хвоста) списку:
- Якщо список порожній, новий вузол стає і головою, і хвостом.
- В іншому випадку вказівник
nextпоточного хвоста оновлюється, щоб вказувати на новий вузол, і хвіст оновлюється на новий вузол. - Значення
lengthзбільшується на 1.
6. prepend(int value)
public void prepend(int value) {
Node newNode = new Node(value);
if (length == 0) {
tail = newNode;
} else {
newNode.next = head;
}
head = newNode;
length++;
}
Пояснення: Цей метод додає новий вузол з заданим значенням value на початок (голову) списку:
- Якщо список порожній, новий вузол стає і головою, і хвостом.
- В іншому випадку вказівник
nextнового вузла вказує на поточну голову, і голова оновлюється на новий вузол. - Значення
lengthзбільшується на 1.
7.
removeLast()
public Node removeLast() {
if (length == 0) {
return null;
}
Node current = head;
Node prev = head;
while (current.next != null) {
prev = current;
current = current.next;
}
tail = prev;
tail.next = null;
length--;
if (length == 0) {
head = null;
tail = null;
}
return current;
}
Пояснення: Цей метод видаляє останній вузол зі списку:
- Якщо список порожній, він повертає
null. - Він проходить через список, щоб знайти останній вузол і оновлює вказівник
tailна попередній вузол. - Вказівник
nextнового хвоста встановлюється вnull, а довжина зменшується на 1. - Якщо список стає порожнім, вказівники на голову та хвіст встановлюються в
null.
8. removeFirst()
public Node removeFirst() {
if (length == 0) {
return null;
}
Node current = head;
head = head.next;
current.next = null;
length--;
if (length == 0) {
head = null;
tail = null;
}
return current;
}
Пояснення: Цей метод видаляє перший вузол (голову) зі списку:
- Якщо список порожній, він повертає
null. - Він оновлює вказівник голови на наступний вузол і встановлює вказівник
nextвидаленого вузла вnull. - Якщо список стає порожнім, вказівники на голову та хвіст встановлюються в
null.
9. get(int index)
public Node get(int index) {
if (index < 0 || index >= length) {
return null;
}
Node current = head;
for (int i = 0; i < index; i++) {
current = current.next;
}
return current;
}
Пояснення: Цей метод отримує вузол за конкретним індексом:
- Він перевіряє, чи є індекс дійсним (в межах списку).
- Потім він проходить через список, щоб досягти вузла за вказаним індексом і повертає його.
10. set(int index, int value)
public boolean set(int index, int value) {
Node current = get(index);
if (current != null) {
current.value = value;
return true;
}
return false;
}
Пояснення: Цей метод встановлює значення вузла на заданому індексі:
- Він отримує вузол за вказаним індексом за допомогою методу
get(). - Якщо вузол існує, оновлює його значення і повертає
true. - Якщо вузол не існує, повертає
false.
11. insert(int index, int value)
public boolean insert(int index, int value) {
if (index < 0 || index > length) {
return false;
}
if (index == 0) {
prepend(value);
} else if (index == length) {
append(value);
} else {
Node newNode = new Node(value);
Node prev = get(index - 1);
newNode.next = prev.next;
prev.next = newNode;
length++;
}
return true;
}
Пояснення: Цей метод вставляє новий вузол на вказаний індекс:
- Він перевіряє, чи є індекс дійсним.
- Якщо індекс 0, то додає вузол на початок.
- Якщо індекс дорівнює довжині, додає вузол в кінець.
- В іншому випадку, вставляє новий вузол між двома існуючими вузлами, оновлюючи вказівники
next.
12. remove(int index)
public Node remove(int index) {
if (index < 0 || index >= length) {
return null;
}
if (index == 0) {
return removeFirst();
} else if (index == length - 1) {
return removeLast();
}
Node prev = get(index - 1);
Node current = prev.next;
prev.next = current.next;
current.next = null;
length--;
return current;
}
Пояснення: Цей метод видаляє вузол за вказаним індексом:
- Він перевіряє, чи є індекс дійсним.
- Якщо індекс 0, то видаляє перший вузол.
- Якщо індекс останній, видаляє останній вузол.
- В іншому випадку, видаляє вузол зі списку, оновлюючи вказівники
next.
13.
reverse()
public void reverse() {
Node current = head;
head = tail;
tail = current;
Node before = null;
Node after;
for (int i = 0; i < length; i++) {
after = current.next;
current.next = before;
before = current;
current = after;
}
}
Пояснення: Цей метод змінює порядок вузлів у списку на зворотний:
- Він міняє місцями голову і хвіст списку.
- Потім проходить через список і змінює напрямок вказівника
nextкожного вузла, щоб перевернути порядок вузлів.
Висновок
Реалізувавши ці методи, ми можемо виконувати різні операції зі списком, такі як додавання, видалення, отримання та зміна вузлів на будь-якій позиції.
Зв’язні списки (Linked lists) особливо корисні, коли нам потрібно ефективно виконувати операції вставки та видалення елементів, не турбуючись про зсув елементів, як це відбувається в масивах.
Повний клас
package datastructures.linkedList;
public class LinkedList {
private Node head;
private Node tail;
private int length;
/**
* Клас вузла
*/
static class Node {
int value;
Node next;
/**
* Конструктор
*
* @param value - значення для вузла
*/
Node(int value) {
this.value = value;
}
}
/**
* Конструктор для створення нового екземпляра зв’язного списку
*
* @param value - перше значення, яке додається до зв’язного списку
*/
public LinkedList(int value) {
Node newNode = new Node(value);
head = newNode;
tail = newNode;
length = 1;
}
/**
* Виводить значення вузлів у зв’язному списку
*/
public void printList() {
Node temp = head;
while (temp != null) {
System.out.println(temp.value);
temp = temp.next;
}
}
/**
* Допоміжний метод для отримання значення голови зв’язного списку
*/
public void getHead() {
System.out.println("Голова: " + head.value);
}
/**
* Допоміжний метод для отримання значення хвоста зв’язного списку
*/
public void getTail() {
System.out.println("Хвіст: " + tail.value);
}
/**
* Допоміжний метод для отримання довжини зв’язного списку
*/
public void getLength() {
System.out.println("Довжина: " + length);
}
/**
* Додає вузол в кінець зв’язного списку
* Ця операція має складність O(1), тобто є сталою
*
* @param value - значення для додавання
*/
public void append(int value) {
Node newNode = new Node(value);
if (length == 0) {
head = newNode;
} else {
tail.next = newNode;
}
tail = newNode;
length++;
}
/**
* Додає вузол на початок зв’язного списку
* Ця операція має складність O(1), тобто є сталою
*
* @param value - значення для додавання
*/
public void prepend(int value) {
Node newNode = new Node(value);
if (length == 0) {
tail = newNode;
} else {
newNode.next = head;
}
head = newNode;
length++;
}
/**
* Видаляє останній елемент зі зв’язного списку
* Ця операція має складність O(n), оскільки потрібно пройти
* через всі елементи списку
*
* @return Node
*/
public Node removeLast() {
if (length == 0) {
return null;
}
Node current = head;
Node prev = head;
while (current.next != null) {
prev = current;
current = current.next;
}
tail = prev;
tail.next = null;
length--;
if (length == 0) {
head = null;
tail = null;
}
return current;
}
/**
* Видаляє перший елемент зі зв’язного списку
* Ця операція має складність O(1), тобто є сталою
*
* @return Node
*/
public Node removeFirst() {
if (length == 0) {
return null;
}
Node current = head;
head = head.next;
current.next = null;
length--;
if (length == 0) {
head = null;
tail = null;
}
return current;
}
/**
* Повертає вузол за вказаним індексом у зв’язному списку
* Ця операція має складність O(n), оскільки потрібно пройти
* через 'n' елементів списку
*
* @param index - індекс, з якого потрібно отримати значення
* @return Node
*/
public Node get(int index) {
if (index < 0 || index >= length) {
return null;
}
Node current = head;
for (int i = 0; i < index; i++) {
current = current.next;
}
return current;
}
/**
* Заміщає значення у вузлі за вказаним індексом у зв’язному списку
* Ця операція має складність O(n), оскільки потрібно пройти
* через 'n' елементів списку для зміни його значення
*
* @param index - індекс, який потрібно змінити
* @param value - нове значення для додавання на цьому індексі
* @return Node
*/
public boolean set(int index, int value) {
Node current = get(index);
if (current != null) {
current.value = value;
return true;
}
return false;
}
/**
* Вставляє вузол за вказаним індексом у зв’язному списку
* Ця операція має складність O(n).
*
* @param index - індекс для вставки
* @param value - нове значення, яке потрібно вставити за цим індексом
* @return boolean
*/
public boolean insert(int index, int value) {
if (index < 0 || index > length) {
return false;
}
if (index == 0) {
prepend(value);
} else if (index == length) {
append(value);
} else {
Node newNode = new Node(value);
Node prev = get(index - 1);
newNode.next = prev.next;
prev.next = newNode;
length++;
}
return true;
}
/**
* Видаляє вузол за вказаним індексом у зв’язному списку
*
* @param index - індекс, за яким потрібно видалити значення
* @return Node
*/
public Node remove(int index) {
if (index < 0 || index >= length) {
return null;
}
if (index == 0) {
return removeFirst();
} else if (index == length - 1) {
return removeLast();
}
Node prev = get(index - 1);
Node current = prev.next;
prev.next = current.next;
current.next = null;
length--;
return current;
}
/**
* Перевертає зв’язний список
*/
public void reverse() {
Node current = head;
head = tail;
tail = current;
Node before = null;
Node after;
for (int i = 0; i < length; i++) {
after = current.next;
current.next = before;
before = current;
current = after;
}
}
}
Для подальшого вивчення та практики з алгоритмами і структурами даних на Java, не соромтеся перевірити мій репозиторій на GitHub:
Цей блог охоплює основні функціональні можливості та реалізацію односпрямованого зв’язного списку на Java, що є важливою концепцією для співбесід та розуміння основних структур даних!
Перекладено з: 👨💻 Implementing a Linked List in Java: A Step-by-Step Guide for Interview Preparation 📚