이중 연결 목록 : 맨 앞에 노드 추가. Geeksforgeeks (Java 코드)에서

Question

이중 연결 목록 앞에 노드를 추가하는 코드입니다. 여기서 이해하지 못하는 것은 4 단계입니다. 바로 여기에서 new_Node의 주소를 변수 head.prev에 저장하고있는 것 같습니다. 이제 head.prev 변수는 새 노드를 보유합니다. 변수 'head'도 new_node를 보유하기 때문에 이것은 의미가 없습니다. 이제 동일한 주소를 가리키는 두 개의 변수가 있습니다.

어쨌든,이 코드가 new_node = head.prev라고하더라도 말이되지 않습니다. 왜냐하면 head.prev는이 시점에서 null이되고 new_node는 null을 가리킬 것이기 때문입니다.

// 이중 연결 목록을위한 클래스 public class DLL {Node head; // 목록 헤드

/* Doubly Linked list Node*/
class Node { 
    int data; 
    Node prev; 
    Node next; 

    // Constructor to create a new node 
    // next and prev is by default initialized as null 
    Node(int d) { data = d; } 
} 
// Adding a node at the front of the list 
public void push(int new_data) 
{ 
/* 1. allocate node  
* 2. put in the data */
    Node new_Node = new Node(new_data); 

/* 3. Make next of new node as head and previous as NULL */
new_Node.next = head; 
new_Node.prev = null; 

/* 4. change prev of head node to new node */
    if (head != null) 
        head.prev = new_Node; 

/* 5. move the head to point to the new node */
    head = new_Node; 
} 

}

Answer 1

prev이전 헤드를 새 헤드 에 연결하려면 4 단계가 필요합니다 .

이것은 3 단계 이후의 상황입니다.

그런 다음 4 단계 후에 prev이전 헤드 (null이었던)가 새 헤드를 가리 키도록 설정됩니다.

그런 다음 5 단계는 헤드가 새 노드 (새 헤드)를 가리 킵니다.

Answer 2

경우 head.prev != null한 다음 head목록의 첫 번째 요소가 아닙니다. 이것은 전제 조건으로 확인 IllegalStateException해야하며를 던져야합니다. 첫 번째 위치에 대한 포인터를 복원해야하므로 삽입의 추가 처리는 무의미합니다.

3 단계 후 new_node설정이 완료 되고는 이전의 첫 번째 요소 인 이제 두 번째 요소에 new_node단방향으로 연결됩니다 . 이중 링크를 완료하려면을 새 선행 작업으로 설정해야합니다 . 즉 당신이를 생략하면 4 단계가하는 일입니다 .new_node.nextheadhead.prevheadif

Answer 3

public class DLL {

    private Node head;
    private Node tail;

    public void addFirst(int val) {
        Node node = new Node(val);

        if (head == null)
            tail = node;
        else {
            node.next = head;
            head.prev = node;
        }

        head = node;
    }

    public void addLast(int val) {
        Node node = new Node(val);

        if (tail == null)
            head = node;
        else {
            tail.next = node;
            node.prev = tail;
        }

        tail = node;
    }

    private static final class Node {

        private final int val;
        private Node prev;
        private Node next;

        public Node(int val) {
            this.val = val;
        }
    }
}