Въведение
Свързаните списъци са основна структура от данни в компютърното програмиране, която предлага динамичен и ефективен начин за обработка на данни. В това ръководство за начинаещи ще проучим основите на свързаните списъци в Java, включително предимствата им, как да ги внедрим и някои общи операции. До края на тази статия ще имате солидно разбиране за свързаните списъци и как да ги използвате във вашите Java проекти.
Какво е свързан списък?
Дефиниция на свързан списък
Свързаният списък е линейна структура от данни, където всеки елемент (наречен възел) съдържа данни и препратка (или връзка) към следващия възел в последователността. За разлика от масивите, свързаните списъци не изискват непрекъснато разпределение на паметта, което позволява по-ефективно използване на ресурсите на паметта. Освен това размерът на свързания списък може лесно да се променя по време на изпълнение, което го прави по-гъвкав от масивите.
Типове свързани списъци:
Има различни видове свързани списъци, като например:
- Списък с отделни връзки: Всеки възел съдържа препратка към следващия възел.
- Двойно свързан списък:Всеки възел съдържа препратки както към следващия, така и към предишния възел.
- Кръгов свързан списък: Последният възел в списъка сочи обратно към първия възел, образувайки цикъл.
Внедряване на свързан списък в Java
Създаване на клас възел
Класът Node е гръбнакът на свързан списък, тъй като представлява отделните елементи в списъка. Ето пример за прост клас Node в Java:
public class Node {
int data;
Node next;
public Node(int data) {
this.data = data;
this.next = null;
}
}
Изграждане на класа на свързания списък
Класът Linked List съдържа методи за добавяне, премахване и показване на елементи. Ето основен клас Linked List в Java:
public class LinkedList {
Node head;
public LinkedList() {
head = null;
}
// Methods for adding, removing, and displaying elements go here
}
Общи операции със свързани списъци
Добавяне на елементи
За да добавите елементи към свързан списък, можете да ги вмъкнете в началото, края или конкретен индекс. Ето примерни кодове за всеки сценарий:
Добавяне в началото
public void addFirst(int data) {
Node newNode = new Node(data);
newNode.next = head;
head = newNode;
}
Добавяне в края
public void addLast(int data) {
Node newNode = new Node(data);
if (head == null) {
head = newNode;
return;
}
Node last = head;
while (last.next != null) {
last = last.next;
}
last.next = newNode;
}
Добавяне на определен индекс
public void addAtIndex(int index, int data) {
if (index == 0) {
addFirst(data);
return;
}
Node newNode = new Node(data);
Node current = head;
for (int i = 0; i < index - 1; i++) {
if (current == null) {
throw new IndexOutOfBoundsException("Invalid index");
}
current = current.next;
}
newNode.next = current.next;
current.next = newNode;
}
Премахване на елементи
За да премахнете елементи от свързан списък, можете да изтриете първото срещане, последното появяване или конкретен индекс. Ето примерни кодове за всяка ситуация:
Премахване на първото срещане
public void removeFirstOccurrence(int data) {
if (head == null) {
return; // List is empty
}
if (head.data == data) {
head = head.next;
return;
}
Node current = head;
while (current.next != null) {
if (current.next.data == data) {
current.next = current.next.next;
return;
}
current = current.next;
}
}
Премахване на последното срещане
public void removeLastOccurrence(int data) {
Node lastOccurrence = null;
Node current = head;
int index = 0, lastIndex = -1;
while (current != null) {
if (current.data == data) {
lastOccurrence = current;
lastIndex = index;
}
current = current.next;
index++;
}
if (lastOccurrence != null) {
removeAtIndex(lastIndex);
}
}
Премахване при определен индекс
public void removeAtIndex(int index) {
if (head == null) {
return; // List is empty
}
if (index == 0) {
head = head.next;
return;
}
Node current = head;
for (int i = 0; i < index - 1; i++) {
if (current == null || current.next == null) {
throw new IndexOutOfBoundsException("Invalid index");
}
current = current.next;
}
current.next = current.next.next;
}
Търсене и достъп до елементи
За да търсите елементи в рамките на свързан списък и да осъществявате достъп до тях по индекс, можете да използвате следните методи:
Търсене на елемент
public boolean contains(int data) {
Node current = head;
while (current != null) {
if (current.data == data) {
return true;
}
current = current.next;
}
return false;
}
Достъп до елемент чрез индекс
public int get(int index) {
Node current = head;
for (int i = 0; i < index; i++) {
if (current == null) {
throw new IndexOutOfBoundsException("Invalid index");
}
current = current.next;
}
return current.data;
}
Обхождане на свързан списък
Обхождането на свързан списък включва итерация през неговите елементи. Можете да използвате цикъл или вграден итератор на Java за тази цел:
Преминаване с помощта на цикъл
public void display() {
Node current = head;
while (current != null) {
System.out.print(current.data + " -> ");
current = current.next;
}
System.out.println("null");
}
Заключение
Разбирането на свързаните списъци като структура от данни в Java е от решаващо значение за всеки програмист. Като научите как да внедрявате и манипулирате свързани списъци, можете ефективно да боравите с динамични набори от данни във вашите проекти. Практикувайте внедряване на свързани списъци в Java и проучете допълнителни ресурси, за да развиете допълнително уменията си. С продължителна практика скоро ще овладеете тази многостранна и мощна структура от данни.
