Попередня умова: Як і масиви, пов’язаний список є лінійною структурою даних. На відміну від масивів, елементи зв’язаного списку не зберігаються в безперервному місці, елементи зв’язуються за допомогою вказівників, як показано нижче.

Як і масиви, пов’язаний список є лінійною структурою даних. На відміну від масивів, елементи зв’язаного списку не зберігаються в безперервному місці, елементи зв’язуються за допомогою вказівників, як показано нижче.

У Java LinkedList можна представити як клас, а Node – як окремий клас. Клас LinkedList містить посилання типу класу Node.

Java

class> LinkedList {> > Node head;> // head of list> > /* Linked list Node*/> > static> 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);> > > > // 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 

Обхід: Для обходу нижче наведено функцію загального призначення printList(), яка друкує будь-який заданий список, обходячи список від головного вузла до останнього.

Реалізація:

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 

Видалення за КЛЮЧОМ:

Процес видалення можна розуміти так:

Має бути зроблено:

Якщо задано «ключ», видалити перше входження цього ключа у пов’язаному списку .

Як це зробити:

Щоб видалити вузол зі зв’язаного списку, виконайте наступні дії.

1. Шукайте ключ за його першим входженням у списку
2. Тепер може бути будь-яка з 3 умов:
   • Випадок 1: ключ знайдено на голова
     1. У цьому випадку змініть голову вузла на наступний вузол поточної голови.
        
     2. Звільніть пам'ять заміненого головного вузла.
   • Випадок 2: ключ знайдено посередині або в кінці, за винятком голова
     1. У цьому випадку знайдіть попередній вузол вузла, який потрібно видалити.
     2. Змінити наступний попередній вузол на наступний вузол поточного вузла.
     3. Звільніть пам'ять заміненого вузла.
   • Випадок 3: ключ не знайдено в списку
     1. У цьому випадку операції робити не потрібно.

Реалізація:

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;> > }> > System.out.println();> > }> > // **************DELETION BY KEY**************> > // Method to delete a node in the LinkedList by KEY> > public> static> LinkedList deleteByKey(LinkedList list,> > int> key)> > {> > // Store head node> > Node currNode = list.head, prev => null> ;> > //> > // CASE 1:> > // If head node itself holds the key to be deleted> > if> (currNode !=> null> && currNode.data == key) {> > list.head = currNode.next;> // Changed head> > // Display the message> > System.out.println(key +> ' found and deleted'> );> > // Return the updated List> > return> list;> > }> > //> > // CASE 2:> > // If the key is somewhere other than at head> > //> > // Search for the key to be deleted,> > // keep track of the previous node> > // as it is needed to change currNode.next> > while> (currNode !=> null> && currNode.data != key) {> > // If currNode does not hold key> > // continue to next node> > prev = currNode;> > currNode = currNode.next;> > }> > // If the key was present, it should be at currNode> > // Therefore the currNode shall not be null> > if> (currNode !=> null> ) {> > // Since the key is at currNode> > // Unlink currNode from linked list> > prev.next = currNode.next;> > // Display the message> > System.out.println(key +> ' found and deleted'> );> > }> > //> > // CASE 3: The key is not present> > //> > // If key was not present in linked list> > // currNode should be null> > if> (currNode ==> null> ) {> > // Display the message> > System.out.println(key +> ' not found'> );> > }> > // return the List> > return> list;> > }> > // **************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);> > //> > // ******DELETION BY KEY******> > //> > // Delete node with value 1> > // In this case the key is ***at head***> > deleteByKey(list,> 1> );> > // Print the LinkedList> > printList(list);> > // Delete node with value 4> > // In this case the key is present ***in the> > // middle***> > deleteByKey(list,> 4> );> > // Print the LinkedList> > printList(list);> > // Delete node with value 10> > // In this case the key is ***not present***> > deleteByKey(list,> 10> );> > // Print the LinkedList> > printList(list);> > }> }>

Вихід

LinkedList: 1 2 3 4 5 6 7 8 1 found and deleted LinkedList: 2 3 4 5 6 7 8 4 found and deleted LinkedList: 2 3 5 6 7 8 10 not found LinkedList: 2 3 5 6 7 8 

Видалення на позиції:

Цей процес видалення можна розуміти так:

Має бути зроблено:
Враховуючи а «позиція» , видаліть вузол у цій позиції зі зв’язаного списку .
Як це зробити:

Щоб це зробити, виконайте наведені нижче дії.

1. Перейдіть по списку, підрахувавши індекси вузлів
2. Для кожного індексу встановіть відповідність індексу позиції
3. Тепер може бути будь-яка з 3 умов:
   • Випадок 1: Позиція дорівнює 0, тобто голова має бути видалена
     1. У цьому випадку змініть голову вузла на наступний вузол поточної голови.
        
     2. Звільніть пам'ять заміненого головного вузла.
   • Випадок 2: позиція більша за 0, але менша за розмір списку, тобто в середині чи останньому місці, за винятком початку
     1. У цьому випадку знайдіть попередній вузол вузла, який потрібно видалити.
        
     2. Змінити наступний із попереднього вузла на наступний вузол поточного вузла.
     3. Звільніть пам'ять заміненого вузла.
   • Випадок 3: позиція більша за розмір списку, тобто позиція не знайдена в списку
     1. У цьому випадку операції робити не потрібно.

Реалізація:

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;> > }> > System.out.println();> > }> > // Method to delete a node in the LinkedList by POSITION> > public> static> LinkedList> > deleteAtPosition(LinkedList list,> int> index)> > {> > // Store head node> > Node currNode = list.head, prev => null> ;> > //> > // CASE 1:> > // If index is 0, then head node itself is to be> > // deleted> > if> (index ==> 0> && currNode !=> null> ) {> > list.head = currNode.next;> // Changed head> > // Display the message> > System.out.println(> > index +> ' position element deleted'> );> > // Return the updated List> > return> list;> > }> > //> > // CASE 2:> > // If the index is greater than 0 but less than the> > // size of LinkedList> > //> > // The counter> > int> counter => 0> ;> > // Count for the index to be deleted,> > // keep track of the previous node> > // as it is needed to change currNode.next> > while> (currNode !=> null> ) {> > if> (counter == index) {> > // Since the currNode is the required> > // position Unlink currNode from linked list> > prev.next = currNode.next;> > // Display the message> > System.out.println(> > index +> ' position element deleted'> );> > break> ;> > }> > else> {> > // If current position is not the index> > // continue to next node> > prev = currNode;> > currNode = currNode.next;> > counter++;> > }> > }> > // If the position element was found, it should be> > // at currNode Therefore the currNode shall not be> > // null> > //> > // CASE 3: The index is greater than the size of the> > // LinkedList> > //> > // In this case, the currNode should be null> > if> (currNode ==> null> ) {> > // Display the message> > System.out.println(> > index +> ' position element not found'> );> > }> > // return the List> > return> list;> > }> > // **************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);> > //> > // ******DELETION AT POSITION******> > //> > // Delete node at position 0> > // In this case the key is ***at head***> > deleteAtPosition(list,> 0> );> > // Print the LinkedList> > printList(list);> > // Delete node at position 2> > // In this case the key is present ***in the> > // middle***> > deleteAtPosition(list,> 2> );> > // Print the LinkedList> > printList(list);> > // Delete node at position 10> > // In this case the key is ***not present***> > deleteAtPosition(list,> 10> );> > // Print the LinkedList> > printList(list);> > }> }>

Вихід

LinkedList: 1 2 3 4 5 6 7 8 0 position element deleted LinkedList: 2 3 4 5 6 7 8 2 position element deleted LinkedList: 2 3 5 6 7 8 10 position element not found LinkedList: 2 3 5 6 7 8 

Усі операції:

Нижче наведено повну програму, яка застосовує кожну операцію разом:

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> ;> > }> > }> > // **************INSERTION**************> > // 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;> > }> > // **************TRAVERSAL**************> > // 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;> > }> > System.out.println(> ' '> );> > }> > // **************DELETION BY KEY**************> > // Method to delete a node in the LinkedList by KEY> > public> static> LinkedList deleteByKey(LinkedList list,> > int> key)> > {> > // Store head node> > Node currNode = list.head, prev => null> ;> > //> > // CASE 1:> > // If head node itself holds the key to be deleted> > if> (currNode !=> null> && currNode.data == key) {> > list.head = currNode.next;> // Changed head> > // Display the message> > System.out.println(key +> ' found and deleted'> );> > // Return the updated List> > return> list;> > }> > //> > // CASE 2:> > // If the key is somewhere other than at head> > //> > // Search for the key to be deleted,> > // keep track of the previous node> > // as it is needed to change currNode.next> > while> (currNode !=> null> && currNode.data != key) {> > // If currNode does not hold key> > // continue to next node> > prev = currNode;> > currNode = currNode.next;> > }> > // If the key was present, it should be at currNode> > // Therefore the currNode shall not be null> > if> (currNode !=> null> ) {> > // Since the key is at currNode> > // Unlink currNode from linked list> > prev.next = currNode.next;> > // Display the message> > System.out.println(key +> ' found and deleted'> );> > }> > //> > // CASE 3: The key is not present> > //> > // If key was not present in linked list> > // currNode should be null> > if> (currNode ==> null> ) {> > // Display the message> > System.out.println(key +> ' not found'> );> > }> > // return the List> > return> list;> > }> > // **************DELETION AT A POSITION**************> > // Method to delete a node in the LinkedList by POSITION> > public> static> LinkedList> > deleteAtPosition(LinkedList list,> int> index)> > {> > // Store head node> > Node currNode = list.head, prev => null> ;> > //> > // CASE 1:> > // If index is 0, then head node itself is to be> > // deleted> > if> (index ==> 0> && currNode !=> null> ) {> > list.head = currNode.next;> // Changed head> > // Display the message> > System.out.println(> > index +> ' position element deleted'> );> > // Return the updated List> > return> list;> > }> > //> > // CASE 2:> > // If the index is greater than 0 but less than the> > // size of LinkedList> > //> > // The counter> > int> counter => 0> ;> > // Count for the index to be deleted,> > // keep track of the previous node> > // as it is needed to change currNode.next> > while> (currNode !=> null> ) {> > if> (counter == index) {> > // Since the currNode is the required> > // position Unlink currNode from linked list> > prev.next = currNode.next;> > // Display the message> > System.out.println(> > index +> ' position element deleted'> );> > break> ;> > }> > else> {> > // If current position is not the index> > // continue to next node> > prev = currNode;> > currNode = currNode.next;> > counter++;> > }> > }> > // If the position element was found, it should be> > // at currNode Therefore the currNode shall not be> > // null> > //> > // CASE 3: The index is greater than the size of the> > // LinkedList> > //> > // In this case, the currNode should be null> > if> (currNode ==> null> ) {> > // Display the message> > System.out.println(> > index +> ' position element not found'> );> > }> > // return the List> > return> list;> > }> > // **************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);> > //> > // ******DELETION BY KEY******> > //> > // Delete node with value 1> > // In this case the key is ***at head***> > deleteByKey(list,> 1> );> > // Print the LinkedList> > printList(list);> > // Delete node with value 4> > // In this case the key is present ***in the> > // middle***> > deleteByKey(list,> 4> );> > // Print the LinkedList> > printList(list);> > // Delete node with value 10> > // In this case the key is ***not present***> > deleteByKey(list,> 10> );> > // Print the LinkedList> > printList(list);> > //> > // ******DELETION AT POSITION******> > //> > // Delete node at position 0> > // In this case the key is ***at head***> > deleteAtPosition(list,> 0> );> > // Print the LinkedList> > printList(list);> > // Delete node at position 2> > // In this case the key is present ***in the> > // middle***> > deleteAtPosition(list,> 2> );> > // Print the LinkedList> > printList(list);> > // Delete node at position 10> > // In this case the key is ***not present***> > deleteAtPosition(list,> 10> );> > // Print the LinkedList> > printList(list);> > }> }>

Вихід

LinkedList: 1 2 3 4 5 6 7 8 1 found and deleted LinkedList: 2 3 4 5 6 7 8 4 found and deleted LinkedList: 2 3 5 6 7 8 10 not found LinkedList: 2 3 5 6 7 8 0 position element deleted LinkedList: 3 5 6 7 8 2 position element deleted LinkedList: 3 5 7 8 10 position element not found LinkedList: 3 5 7 8