이중 연결된 목록에서 노드를 제거하는 방법은 무엇입니까?

Question

이중 연결 목록에서 주어진 노드 ("Jack"이라는 노드)를 제거하는 메서드를 만들어야합니다.

연결리스트 클래스 :

class DoublyLinkedList 
{ 
    public Node head, current; 

    public void AddNode(object n) // add a new node 
    { 
     if (head == null) 
     { 
      head = new Node(n); //head is pointed to the 1st node in list 
      current = head; 
     } 
     else 
     { 
      while (current.next != null) 
      { 
       current = current.next; 
      } 

      current.next = new Node(n, current); //current is pointed to the newly added node 
     } 
    } 

    public void RemoveNode(object n) 
    { 

    } 

    public String PrintNode() // print nodes 
    { 
     String Output = ""; 

     Node printNode = head; 
     if (printNode != null) 
     { 
      while (printNode != null) 
      { 
       Output += printNode.data.ToString() + "\r\n"; 
       printNode = printNode.next; 
      } 
     } 
     else 
     { 
      Output += "No items in Doubly Linked List"; 
     } 
     return Output; 
    } 

} 

버튼 코드를 실행 : 당신이 볼 수있는 그리고 내가 "잭"노드를 제거 할 나는 이미 3 개 노드를 추가 한

여기 내 코드입니다.

private void btnExecute_Click(object sender, EventArgs e) 
    { 
     DoublyLinkedList dll = new DoublyLinkedList(); 
     //add new nodes 
     dll.AddNode("Tom"); 
     dll.AddNode("Jack"); 
     dll.AddNode("Mary"); 
     //print nodes 
     txtOutput.Text = dll.PrintNode(); 

    } 

Answer 1

1. n
   1. n.Next 경우 노드 찾기, null하지 n.Prev이 null없는 경우, n.Prev
   2. 에 n.Next.Prev을 설정 n.Next
   3. n == head 경우에 n.Prev.Next을 설정 n.Next에 head 설정

기본적으로, 당신은 당신이 제거 할 노드를 찾아, 그 오른쪽에있는 노드의 왼쪽 지점에 노드를 만들고, 그 반대의 경우도 마찬가지입니다. 노드 n를 찾으려면

, 당신은 같은 것을 할 수 있습니다

public bool Remove(object value) 
{ 
    Node current = head; 

    while(current != null && current.Data != value) 
     current = current.Next; 

    //value was not found, return false 
    if(current == null) 
     return false; 

    //... 
} 

참고 :이 알고리즘은 일반적으로 두 불변을 포함한다. 항상 첫 번째 노드의 Prev 속성과 마지막 노드의 Next 속성이 null인지 확인해야합니다.이 노드는 첫 번째 노드 앞에 노드가없고 마지막 노드 다음에 노드가 없습니다.

Answer 2

코드에 Previous 포인터가 포함되어 있어야 이중 연결 목록이됩니다.

public void RemoveNode(object n) 
{ 
    Node lcurrent = head; 

    while(lcurrent!=null && lcurrent.Data!=n) //assuming data is an object 
    { 
     lcurrent = lcurrent.Next; 
    } 
    if(lcurrent != null) 
    { 
     if(lcurrent==current) current = current.Previous; //update current 
     if(lcurrent==head) 
     { 
      head = lcurrent.Next; 
     } 
     else 
     { 
      lcurrent.Previous.Next = lcurrent.Next; 
      lcurrent.Next.Previous = lcurrent.Previous; 
      lcurrent.Next = null; 
      lcurrent.Previous = null; 
     } 
    } 
}