Реализация связанного списка в Java с использованием класса
Предварительное условие: структура данных связанного списка
Подобно массивам, связанный список представляет собой линейную структуру данных. В отличие от массивов, элементы связанного списка не хранятся в непрерывном месте, элементы связаны с помощью указателей, как показано ниже.
In Java, LinkedList can be represented as a class and a Node as a separate class. The LinkedList class contains a reference of Node class type.
Java
class LinkedList { Node head; // head of list /* Linked list Node*/ class Node { int data; Node next; // Constructor to create a new node // Next is by default initialized // as null Node(int d) { data = d; } }} |
Создание и вставка
В этой статье вставка в список выполняется в конце, то есть новый узел добавляется после последнего узла данного связанного списка. Например, если данный связанный список 5-> 10-> 15-> 20-> 25 и 30 должен быть вставлен, то связанный список станет 5-> 10-> 15-> 20-> 25-> 30 .
Поскольку связанный список обычно представлен указателем его заголовка, необходимо пройти по списку до последнего узла, а затем изменить предпоследний узел на новый узел.
Java
import java.io.*; // Java program to implement// a Singly Linked Listpublic class LinkedList { Node head; // head of list // Linked list Node. // This inner class is made static // so that main() can access it static class Node { int data; Node next; // Constructor Node(int d) { data = d; next = null; } } // Method to insert a new node public static LinkedList insert(LinkedList list, int data) { // Create a new node with given data Node new_node = new Node(data); new_node.next = null; // If the Linked List is empty, // then make the new node as head if (list.head == null) { list.head = new_node; } else { // Else traverse till the last node // and insert the new_node there Node last = list.head; while (last.next != null) { last = last.next; } // Insert the new_node at last node last.next = new_node; } // Return the list by head return list; } // Method to print the LinkedList. public static void printList(LinkedList list) { Node currNode = list.head; System.out.print("LinkedList: "); // Traverse through the LinkedList while (currNode != null) { // Print the data at current node System.out.print(currNode.data + " "); // Go to next node currNode = currNode.next; } } // Driver code public static void main(String[] args) { /* Start with the empty list. */ LinkedList list = new LinkedList(); // // ******INSERTION****** // // Insert the values list = insert(list, 1); list = insert(list, 2); list = insert(list, 3); list = insert(list, 4); list = insert(list, 5); list = insert(list, 6); list = insert(list, 7); list = insert(list, 8); // Print the LinkedList printList(list); }} |
LinkedList: 1 2 3 4 5 6 7 8
Обход
For traversal, below is a general-purpose function printList() that prints any given list by traversing the list from head node to the last.
Java
import java.io.*;// Java program to implement// a Singly Linked Listpublic class LinkedList { Node head; // head of list // Linked list Node. // Node is a static nested class // so main() can access it static class Node { int data; Node next; // Constructor Node(int d) { data = d; next = null; } } // Method to insert a new node public static LinkedList insert(LinkedList list, int data) { // Create a new node with given data Node new_node = new Node(data); new_node.next = null; // If the Linked List is empty, // then make the new node as head if (list.head == null) { list.head = new_node; } else { // Else traverse till the last node // and insert the new_node there Node last = list.head; while (last.next != null) { last = last.next; } // Insert the new_node at last node last.next = new_node; } // Return the list by head return list; } // Method to print the LinkedList. public static void printList(LinkedList list) { Node currNode = list.head; System.out.print("LinkedList: "); // Traverse through the LinkedList while (currNode != null) { // Print the data at current node System.out.print(currNode.data + " "); // Go to next node currNode = currNode.next; } } // **************MAIN METHOD************** // method to create a Singly linked list with n nodes public static void main(String[] args) { /* Start with the empty list. */ LinkedList list = new LinkedList(); // // ******INSERTION****** // // Insert the values list = insert(list, 1); list = insert(list, 2); list = insert(list, 3); list = insert(list, 4); list = insert(list, 5); list = insert(list, 6); list = insert(list, 7); list = insert(list, 8); // Print the LinkedList printList(list); }} |
LinkedList: 1 2 3 4 5 6 7 8