Как удалить первый узел двусвязного списка - PullRequest
Новая
       11

Как удалить первый узел двусвязного списка

0 голосов
/ 14 октября 2019

У меня есть реализация двусвязного списка, и я пытаюсь удалить конкретный узел в данной позиции. Мне удалось удалить второй узел до последнего, но когда я пытаюсь удалить первый узел, он выходит из строя, мне интересно, что не так с моим кодом.

Я уже пробовал это, но все еще не работает 

head.next.previous = null;
head = head.next;

Это мой код 

public class Proses {
    private class Node{
        String Matkul;
        int NilaiUts;
        int NilaiUAS;
        Node previous;  
        Node next;  

        public Node(String Matkul, int Nilai, int NilaiUAS) {
            this.Matkul = Matkul;
            this.NilaiUts = Nilai;
            this.NilaiUAS = NilaiUAS;
        }  
    }  

    Node head, tail = null;    
    public void addNode(String matkul, int Nilai, int NilaiUAS) {   
        Node newNode = new Node(matkul, Nilai, NilaiUAS);   
        if(head == null) {   
            head = tail = newNode;    
            head.previous = null;  
            tail.next = null;  
        } else {  
            tail.next = newNode;   
            newNode.previous = tail;  
            tail = newNode;  
            tail.next = null;  
        }  
    }  

    public void delete(int position){
        if (head == null || n <= 0) 
            return; 
        Node current = head; 
        int i; 
        for (i = 1; current != null && i < position; i++) 
        { 
            current = current.next; 
        } 
        if (current == null) 
            return; 
        deleteNode(head, current); 
    }

    //delete function
    public Node deleteNode(Node head, Node del){
        if (head == null || del == null){
            return null; 
        }
        if (head == del){
            head = del.next;
            del.next.previous = null;
        }
        if (del.next != null){
            del.next.previous = del.previous; 
        }
        if (del.previous != null){
            del.previous.next = del.next; 
        }
        del = null; 
        return head; 
    }
}

Ответы [ 2 ]

1 голос
/ 14 октября 2019

Используя ваш код, если сценарий таков, что он заканчивается 1 узлом (заголовок будет указывать на этот узел), и вы хотите удалить этот узел (т.е. заголовок), код завершится с NullPointerException на 

del.next.previous = null;

, поскольку del.next равен NULL;

Использование позволяет взглянуть на приведенный ниже код для удаления узла из двусвязного списка 

    // Function to delete a node in a Doubly Linked List. 
    // head_ref --> pointer to head node pointer. 
    // del --> data of node to be deleted. 
    void deleteNode(Node head_ref, Node del) 
    { 

        // Base case 
        if (head == null || del == null) { 
            return; 
        } 

        // If node to be deleted is head node 
        if (head == del) { 
            head = del.next; 
        } 

        // Change next only if node to be deleted 
        // is NOT the last node 
        if (del.next != null) { 
            del.next.prev = del.prev; 
        } 

        // Change prev only if node to be deleted 
        // is NOT the first node 
        if (del.prev != null) { 
            del.prev.next = del.next; 
        } 

        // Finally, free the memory occupied by del 
        return; 
    }

код ссылки: https://www.geeksforgeeks.org/delete-a-node-in-a-doubly-linked-list/

0 голосов
/ 14 октября 2019

Проблема с вашим кодом в том, что заголовок не изменяется в функции deleteNode, потому что он передается по значению. Рассмотрим следующий сценарий:

  1. Вы удаляете позицию 1. Голова указывает на узел1, поэтому она хранит адрес узла1. предположим, что это 1001.
  2. Теперь вы вызываете функцию deleteNode со ссылкой на заголовок и currentNode, поэтому ссылка на заголовок передается аргументу функции как передача по значению. поэтому в аргументе функции head содержится адрес 1001.
  3. Теперь вы выполняете операцию удаления, поэтому функция head меняет свою позицию на следующий узел. Но head вашего ученика все еще указывает на первую позицию.
  4. Чтобы преодолеть это, вы можете установить head снова, потому что вы возвращаете его из функции deleteNode. Как:

Изменить код следующим образом 

public void delete(int position){
        if (head == null || n <= 0) 
            return; 
        Node current = head; 
        int i; 
        for (i = 1; current != null && i < position; i++) 
        { 
            current = current.next; 
        } 
        if (current == null) 
            return; 
        head = deleteNode(head, current); 
    }
...