링크 된 목록의 머리글이 더미 노드 여야합니까?

Question

현재 약 5 개의 링크 된 목록을 사용하는 프로그램을 작성하고 있으며 해당 링크 된 목록을 수정하거나 사용하는 약 50 개의 기능이 있습니다. 헤드 노드가 얼마나 정확하게 구현되어야하는지에 대해서는 다소 찢겨 보인다. 나는 더미 헤드 노드를 작성하는 경우 더미 헤드 노드

를 사용

구현 # 1는 headNode는 연결리스트 대표 할 데이터가없는 경우에도 삭제해야하지 않습니다. 다음은이 아이디어를 보여주는 두 개의 서로 다른 가능한 연결 목록입니다.

Format: (object)--name_of_pointer_to_next_object--> (next object) 
(headNode)--headNode.pNext--> (Nothing/NULL) 
(headNode)--headNode.pNext--> (dataNode1)--dataNode1.pNext--> (dataNode2)--dataNode2.pNext--> (Nothing/NULL) 

이 구현의 장점은 헤드 노드가 NULLNothing 또는 (C++에서) 위치를 연결리스트로 작업 기능을 위해, 그들은 경우에 특수 코드가 필요하지 않습니다 것입니다. 다음은이 구현을 사용하여 링크 된 목록의 끝에 노드를 추가하는 예입니다. 나는 headNode을 삭제할 수있는 경우

Public Function AppendNode(theLinkedList as NODE_, theNewNode as NODE_) 
    dim lastNode as NODE_ 

    Set lastNode = theLinkedList 

    Do While Not lastNode.pNext Is Nothing 
     Set lastNode = lastNode.pNext 
    Loop 

    Set lastNode.pNext = theNewNode 
End Function 

구현 # 2 headNode이

를 삭제할 수 있습니다, 이것은 문제를 야기 내가 작성해야 할 코드의 양을 증가시킨다. 아래는 헤드가 데이터를 포함하는 합법적 인 노드 인 것을 제외하고는 동일한 데이터 세트입니다. 여기

Format: (object)--name_of_pointer_to_next_object--> (next object) 
(Nothing/NULL) 
(dataNode1)--dataNode1.pNext--> (dataNode2)--dataNode1.pNext--> (Nothing/NULL) 

그리고

머리 노드 Nothing/ NULL 있음이 가지고 이번에 가능성 조심 것을 제외하고는, 동일한 기능이다.

Public Function AppendNode(theLinkedList as NODE_, theNewNode as NODE_) 
    dim lastNode as NODE_ 

    If theLinkedList Is Nothing Then 
     Set theLinkedList = theNewNode 
    Else 
     Set lastNode = theLinkedList 

     Do While Not lastNode.pNext Is Nothing 
      Set lastNode = lastNode.pNext 
     Loop 

     Set lastNode.pNext = theNewNode 
    End If 
End Function 

분명히, 나는 구현 # 1쪽으로 기대고있다. 연결된 목록을 사용할 때마다 적어도 4 줄 이상의 코드가 더 필요합니다 (이 작업을 수백 번 수행 할 것이라는 가정하에 4 줄을 300 줄로 늘릴 수 있음, 예를 들어 1,200을 작성하는 것을 방지 할 수 있음). 코드 라인), 그리고 아마도 가장 중요한 것은 내 프로그램의 국가 수준을 줄이게 될 것입니다. 내 프로그램에 참여할 수있는 모든 주에만 pNext Is Nothing을 찾아야하며이 프로그램은 20k 줄 정도의 괴물이 될 것이기 때문에이 시점에서 국가의 규모를 줄이는 것이 좋습니다. 복잡한 코드는 많은 국가를 다루어야합니다.

구현 1이 최선의 방법이라고 생각하는 것이 잘못 되었습니까? 구현 # 2가 뛰어난 이유는 하나도 없습니다.

Answer 1

링크 된 목록의 시작과 끝 부분에 특별 예약 노드를 갖는 것은 매우 일반적입니다 (필수는 아니지만). 일반적으로 sentinel node이라고합니다.

제쳐두고, "링크 된 목록을 수정하거나 사용하는 약 50 개의 함수"를 가져 와서 캡슐화 한 클래스로 옮기는 것이 좋습니다.

Dim theLinkedList as NODE_ 
Set theLinkedList = New NODE_ 

'bunch of work with the list 
'bunch of work with the list 
'bunch of work with the list 

Dim theNewNode as NODE_ 
Set theNewNode = New NODE_ 
Set theNewNode.Next = someDataObject 

Call AppendNode(theLinkedList, theNewNode) 

대신 코드를 그냥 다음과 같아야합니다 :

Dim theList As LinkedList 
Set theList = New LinkedList 

'etc 

Call theList.Append(someDataObject) 

차이를 참조

는 는

당신은 다음과 같습니다 코드가없는 것인가? LinkedList의 calss는 세부 정보를 감싸고 숨 깁니다.머리말이나 꼬리에 센티넬 노드가 있는지 등 프로젝트의 모든 코드가 행복하게 인식되지 않도록 처리 할 수 ​​있습니다.