Реализация связанного списка в 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 List public 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 List public 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