단일 링크 목록

Question

인터넷에서 사용할 수있는 몇 가지 예제는 단일 링크 목록에 대해 머리 및 꼬리 노드를 사용하며 일부 예제에서는 그러한 차이점이 존재하지 않습니다.

Answer 1

꼬리 노드는 추가하기 전에 꼬리를 찾기 위해 머리부터 끝까지 반복하지 않고 O (1)을 사용하여 목록의 끝에 항목을 추가하여 O (n) 작업으로 만듭니다 . 따라서 효율성면에서 유용하지만 근본적으로 유용한 목록을 만들어야하는 것은 아닙니다. 나는 예제의 차이가 학문적 순결과 상대적으로 유용한 목록 사이에 있다고 의심한다.

리스트 끝에 새 항목을 추가 할 필요가있을 때 :

Answer 2

는 머리와 꼬리를 모두 유지하는 이유는 속도가 주로하지만 헤드 노드를 기억하지 않고 단독으로 링크 된 목록을 가지고 완전히 무의미한 것 목록의.

목록의 끝을 찾는 일은 쉽지 않지만 목록 수정 중에 그것을 추적하는 데 드는 노력에 비해 너무 많은 시간이 걸립니다.

Answer 3

단일 링크 된 목록은 셀당 포인터가 적은 공간을 사용합니다. 또한 목록의 머리 부분에 추가하고 목록의 첫 번째 부분에서 삭제하는 것이 더 효율적입니다 (다른 링크를 유지할 필요가 없으므로 더 적은 작업).

이중 연결 목록은 목록의 뒷부분에서 삭제 또는 추가하는 것이 더 효율적입니다.

목록을 광범위하게 사용하는 Lisp에서는 단독 연결 목록 만 사용됩니다. 실제로 목록 (Symbolics)과 같은 일부 구현은 목록이 특정 길이보다 짧으면 배열을 사용했습니다.

어떤 것을 사용할지는 응용 프로그램에 따라 다릅니다. 추가 작업이 일반적인 작업이고 속도가 공간보다 더 중요하다면 이중 연결된 목록이 적합 할 수 있습니다. 그러나 단일 링크 된 목록은 대부분의 경우에 더 적합하다고 생각합니다.

Answer 4

다른 사람들이 지적했듯이 꼬리 참조는 일정 시간에 노드를 목록 끝에 추가하는 방법을 제공합니다. 연결된 목록 구현에 꼬리 참조가 없으면 목록의 모든 노드를 반복하여 끝에 추가해야합니다. 다음은 목록에 요소를 추가하는 3 가지 방법을 사용하는 Java Linked List 예제입니다.

• 푸시 (노드 노드)는 - 목록의 시작 부분에 노드를 추가합니다. 헤드 참조로 인해 일정 시간 O (1) 걸립니다.
• add (int index, 노드 노드) - 지정된 인덱스에 노드를 추가합니다. 올바른 인덱스가 발견 될 때까지 각 노드를 반복해야하므로 O (n) 시간이 걸립니다.

• add (노드 노드) - 노드를 목록 끝에 추가합니다. 위에서 설명한 것처럼이 작업은 꼬리 참조를 사용하기 때문에 일정 시간이 걸릴뿐입니다. 꼬리 참조를 추가

  // Insert element at the beginning of the list 
  public void push(T _data) { 
  
      Node<T> addNode = new Node<T>(_data); 
  
      // Set head and tail to new pointer if list is empty 
      if(this.head == null) { 
       this.head = addNode; 
       this.tail = addNode; 
      } else { 
       addNode.setNext(this.head); // Set new node's next pointer to the current head 
       this.head = addNode; // Set head to new node 
      } 
  
      this.numberNodes++; 
  } 
  
  // Insert element at the specified index 
  public void add(int _index, T _data) { 
  
      // Continue if _index is valid 
      if(_index >= 0 && _index <= this.numberNodes) { 
  
       if(_index == 0) { // Push element to front of list if _index is 0 
        this.push(_data); 
       } else if(_index == this.numberNodes) { // Add element to end of list if index is last element 
        this.add(_data); 
       } else { 
  
        // Continue if list is not empty 
        if(this.head != null && this.tail != null) { 
  
         Node<T> addNode = new Node<T>(_data); 
         Node<T> currentNode = this.head.getNext(); 
         Node<T> previousNode = this.head; 
  
         int count = 1; 
         while(currentNode != null) { // Traverse list to find element at _index 
  
          // Insert element when _index is found 
          if(count == _index) { 
           previousNode.setNext(addNode); 
           addNode.setNext(currentNode); 
           this.numberNodes++; 
           break; 
          } 
  
          // Prepare for next iteration 
          previousNode = currentNode; 
          currentNode = currentNode.getNext(); 
          count++; 
         } 
        } 
       } 
      } 
  } 
  
  // Insert element at the end of the list 
  public void add(T _data) { 
  
      Node<T> addNode = new Node<T>(_data); 
  
      // Set head and tail to new pointer if list is empty 
      if(this.head == null) { 
       this.head = addNode; 
       this.tail = addNode; 
      } else { 
       this.tail.setNext(addNode); // Set tail's next pointer to new node 
       this.tail = this.tail.getNext(); // Set tail to new node 
      } 
  
      this.numberNodes++; 
  } 
  

극적으로 링크 된 목록의 마지막에 요소를 삽입하는 시간을 감소시킨다. Java, C++, Python 및 JavaScript에서 꼬리 참조를 사용하여 링크 된 목록 구현에 대해 my blog을 살펴보십시오.