이중 링크 목록 삽입 앞 메서드

Question

내 hw 완료하고 잘못 됐어. 나는 왜 그런지 이해하지 못한다.

내 삽입 앞면에 대해 다음을 수행합니다.

head.next.prev = newNode; 
newNode.next = head; 
newNode.prev = null; 
head.prev = newnode; 
head.next.prev = head; 
size++; 

는하지만 그 대신이 솔루션은 이해가되지 않습니다이 다음 나에게

head.next.prev = newNode(item, head, head.next); // newNode(item,prev,next); So basically head.next.prev is pointing to a newnode here newnode.prev = head and newnode.next = head.next. Ok that make sense. 
head.next = head.next.prev; // huh? 
size++; 

솔루션과 같은 내 솔루션은 완벽하게 논리적이다. head.next.prev = 새 노드로 만들면 head.next.prev = head를 작성해야합니다. 그렇지 않으면 점프 권한이 있습니까? 또한 head.next = head.next.prev; 어떤 의미가 없습니다. 그 줄은 기본적으로 head.prev가 머리 그 자체를 가리키고 있다고 말합니다. 그렇게해서는 안됩니다 head.next.prev = head;

어떤 일이 벌어지고 있는지 지적 해줄 수 있습니까? 내가 솔루션 사이의 형식이 다른 알고 있지만 난 전체 코드는 많은 혼란이있다

아래에 표시되는 논리

에 더 관심이 있어요. 그래서 여기에 머리를 선언하는 방법은

public class DList { 

/** 
* head references the sentinel node. 
* size is the number of items in the list. (The sentinel node does not 
*  store an item.) 
* 
* DO NOT CHANGE THE FOLLOWING FIELD DECLARATIONS. 
*/ 

protected DListNode head; 
protected int size; 

/* DList invariants: 
* 1) head != null. 
* 2) For any DListNode x in a DList, x.next != null. 
* 3) For any DListNode x in a DList, x.prev != null. 
* 4) For any DListNode x in a DList, if x.next == y, then y.prev == x. 
* 5) For any DListNode x in a DList, if x.prev == y, then y.next == x. 
* 6) size is the number of DListNodes, NOT COUNTING the sentinel, 
*  that can be accessed from the sentinel (head) by a sequence of 
*  "next" references. 
*/ 

/** 
* newNode() calls the DListNode constructor. Use this class to allocate 
* new DListNodes rather than calling the DListNode constructor directly. 
* That way, only this method needs to be overridden if a subclass of DList 
* wants to use a different kind of node. 
* @param item the item to store in the node. 
* @param prev the node previous to this node. 
* @param next the node following this node. 
*/ 
protected DListNode newNode(Object item, DListNode prev, DListNode next) { 
return new DListNode(item, prev, next); 
} 

/** 
* DList() constructor for an empty DList. 
*/ 
public DList() { 
head = newNode(null, head, head); 
head.next = head; 
head.prev = head; 
size = 0; 
} 



    public insertfront(Object item){ 
???????????} 

//////////////////// 아래 DlistNoe.java

public class DListNode { 

    /** 
    * item references the item stored in the current node. 
    * prev references the previous node in the DList. 
    * next references the next node in the DList. 
    * 
    * DO NOT CHANGE THE FOLLOWING FIELD DECLARATIONS. 
    */ 

    public Object item; 
    protected DListNode prev; 
    protected DListNode next; 

    /** 
    * DListNode() constructor. 
    * @param i the item to store in the node. 
    * @param p the node previous to this node. 
    * @param n the node following this node. 
    */ 
    DListNode(Object i, DListNode p, DListNode n) { 
    item = i; 
    prev = p; 
    next = n; 
    } 
} 

Answer 1

잘못이 많이있다있다 삽입 코드로 그냥 영어로 읽어 :

head.next.prev = newNode; 

점을 첫 번째 노드의 "이전"을 새로운 노드 (확인)

newNode.next = head; 

포인트 머리에 새 노드의 "다음"에 (? 무엇을)

newNode.prev = null; 

포인트 새로운 노드의 "이전"은 (는 첫 번째 노드, 그래서 그것은 머리를 가리켜 야합니다) null로

head.prev = newnode; 

머리의 "이전"는 null로

포인트가 첫 번째 노드의 이전 머리에

head.next.prev = head; 

포인트 (당신이 접촉하지 말아야 있도록 전면에 삽입하는 것) (당신이 먼저 한 일 취소 step)

이제는 이전 첫 번째 요소를 가리키는 헤드가 있고 이제는 목록의 마지막 요소를 다시 가리키고 있지 않습니다. 그리고 완전히 삽입되지 않은 새로운 요소 ("prev"는 아무것도 가리키고 있지 않으며 "next"는 잘못된 요소를 가리키고 있음).

그래, 정말로 정확하지는 않습니다. 위와 같은 올바른 해결책을 읽으면 더 이해하기 쉬울 것입니다.

Answer 2

링크 된 목록과 같은 구조의 문제는 참조를 수정하기 시작할 때 노드가 손실된다는 것입니다.

그래서 일부 노드의 이름을 지정합니다.

삽입 전에 연결 목록 :

H -> A -> B -> C 
H.next = A 
H.prev = null 
A.next = B 
A.prev = H 
And so on... 

목표 연결리스트 :

DList 불변 주어진 솔루션 기반

H -> N -> A -> B -> C 
H.next = N 
H.prev = null (unchanged) 
A.next = B (unchanged) 
A.prev = N 
N.next = A 
N.prev = H 

, 않는 헤드 노드가 머리에 머물러있는 가치를 가지지 마라.

그럼이 코드를 단계별로하자 :

이

head.next.prev = newNode; // H.next -> A, A.prev = N. This seems fine. 
newNode.next = head;  // N.next = H. What? This doesn't match our goal. 
newNode.prev = null;  // N.prev = null. Also doesn't match our goal. 
head.prev = newnode;  // H.prev = n. Also doesn't match our goal. 
head.next.prev = head; // H.next -> A, looks like you mean this to be N, but its still A. 
          // thus A.prev = H. Also doesn't match our goal. 
size++; 

마지막의 지정된 솔루션을 살펴 보자.

head.next.prev = newNode(item, head, head.next); 
// First the function, H.next -> A, so... 
// N.prev = H. Matches goal. 
// N.next = A. Also matches goal. 
// Then the assignment: 
// head.next -> A, A.prev = N. Matches goal.  
head.next = head.next.prev; 
// head.next -> A, A.prev -> N, H.next = N. Matches goal. 
size++; 

따라서 4 개의 변경된 참조가 모두 설정되었습니다.