Java API의 LinkedList 클래스에있는 "header"

Question

LinkedList 문서를 읽는 중 "헤더"를 사용하는 것에 약간의 혼란이 있습니다. 일반적으로 헤더는 linkedList의 첫 번째 노드입니다. 그러나 여기에서는 '헤더'가 목록의 더미 노드이고 목록의 첫 번째 노드와 마지막 노드를 가리키는 것처럼 보이므로 LinkedList를 순환 노드로 만듭니다. 그게 사실이야?

private transient Entry<E> header = new Entry<E>(null, null, null); 
public LinkedList() { 
    header.next = header.previous = header; 
} 

public E getFirst() { 
    if (size==0) 
     throw new NoSuchElementException(); 

    return header.next.element; 
} 

public E getLast() { 
    if (size==0) 
     throw new NoSuchElementException(); 

    return header.previous.element; 
} 

public E removeFirst() { 
    return remove(header.next); 
} 

Answer 1

순환 목록은 머리글 및 꼬리 포인터를 최상위 구조에 저장하는 것을 피하기위한 저렴한 방법입니다. Java의 LinkedList 구현에 대해서는 잘 모릅니다. 그러나 이것은 확실히 예를 들어 GCC 구현은 std::list입니다.

Answer 2

그러나 여기가 '헤더'처럼 보인다는 목록에서 더미 노드이며 많은 사실이다 목록

의 처음과 마지막 노드를 가리키는

따라서 LinkedList를 원형으로 만듭니다.

구조적으로, 목록은 실제로 원형입니다. 왜냐하면 헤더가 실제로 순환합니다. 이는 구현 세부 사항으로, 두 가지 (header 및 tailPiece) 대신 하나를 선언하지 않도록하는 일반적인 트릭입니다. 동일한 항목이 양쪽 끝 모두에 대해 사용된다는 사실은 목록을 원형으로 만드는 데는 불충분합니다. count이 그렇게하지 못하도록 "외부에서"마지막 노드 주위를 반복 할 수있는 방법이 없습니다.

Answer 3

네 말이 맞아. header은 목록의 머리와 꼬리 모두에 대한 참조를 저장합니다. 이렇게하면 목록의 양쪽 끝에 대해 ​​삭제/추가 /보기와 관련된 작업 비용을 줄일 수 있습니다. 양쪽 끝 부분에 대한 참조의 가용성과 함께

는 getFirst, getLast, removeFirst, removeLast, addFirst, addLast 등과 같은 작업은 목록 탐색이 필요하지 않습니다.

Answer 4

LinkedList의 구현은 s 센티넬 노드를 사용합니다. 그들은 머리와 꼬리 모두에 하나의 센티널을 사용하기로했습니다. 다른 implmentation은 두 개의 분리 된 센티널을 사용합니다.

어느 경우 든, 센티널을 사용하면 나머지 구현 코드가 null을 처리하지 못합니다. 예를 들어, 노드 추가를 고려하십시오. 전초와

Node newNode = ...; 
if (header == null) { 
    header = newNode; 
    tail = newNode; 
} else { 
    newNode.previous = tail; 
    tail.next = newNode; 
    tail = newNode; 
} 

: 센티넬없이

Node newNode = ...; 
newNode.previous = sentinel.previous; 
newNode.next = sentinel; 
sentinel.previous = newNode; 

다음은 Wikipedia article on Sentinel Nodes입니다.