이중 연결 리스트 마지막 삽입

Struct Node_{
	int data; 
	struct Node_* prev;
	struct Node_* next;
}
typedef struct Node_ Node;

Node* head;

//malloc을 통한 노드 생성 및 데이터, NULL 삽입이 반복되므로 함수로 뺀다. 
Node* GetNewNode(int x){
	Node* newNode = (Node*)malloc(sizeOf(Node));
	newNode -> data = x;
	newNode -> prev = NULL;
	newNode -> next = NULL;

	return newNode;
}

void insertAtTail(int x){
	Node* p = head; 
	Node* tmp = GetNewNode(x); //tmp라는 노드포인트 변수가 힙을 가리키게 됨
	if(head == NULL){
		head = tmp;
		return;
	}
	while(p -> next != NULL){ //insertAtHead에는 이 while문이 없다. tail에 삽입이므로 head를 타고 끝 노드로 가기 위한 부분
		p = p -> next;
	}
	p -> next = tmp;
	tmp -> prev = p;
}

int main(){
	Node* head = NULL;
	insertAtTail(2);
	insertAtTail(4);
	insertAtTail(6);
	
}

전체 코드는 다음과 같다.

---

< main >

main을 따라 가보자.

//main
	Node* head = NULL;

Node 포인트 타입의 head가 NULL을 가리킨다.

//main
	insertAtTail(2);

insertAtTail 함수에 파라미터 2를 준다.
insertAtTail이라는 마지막 노드로 데이터를 삽입하는 함수를 자세히 살펴보자.

//insertAtTail function

void insertAtTail(int x){
	Node* p = head; 
	Node* tmp = GetNewNode(x); 
	if(head == NULL){
		head = tmp;
		return;
	}
	while(p -> next != NULL){ //insertAtHead에는 이 while문이 없다. tail에 삽입이므로 head를 타고 끝 노드로 가기 위한 부분
		p = p -> next;
	}
	p -> next = tmp;
	tmp -> prev = p;
}

한 라인씩 살펴보자.

//insertAtTail function
	Node* p = head; 

//insertAtTail function
	Node* tmp = GetNewNode(2); 

//insertAtTail function
	if(head == NULL){
		head = tmp;
		return;
	}

head가 NULL이므로 if 문에 들어간다.

return에 의해 insertAtTail 함수가 종료된다.

함수가 종료되며 insertAtTail에서 선언한 로컬 변수들은 사라지고, free하지 않은 heap만이 남는다.

다시, main이다.

//main 
	insertAtTail(4);

insertAtTail함수에 파라미터로 4를 준다.
insertAtTail함수를 한 라인씩 살펴보자.

//insertAtTail function
	Node* p = head;

//insertAtTail function
	Node* tmp = GetNewNode(4);

head가 NULL이 아니므로 if문에 진입하지 않는다.

//insertAtTail function
	while(p -> next != NULL){ 
		p = p -> next; //다음 노드로 이동
	}

p가 마지막 노드를 가리킬 때까지 이동한다.
현재, p가 주소가 400인 첫 노드를 가리키고 그 노드의 next는 NULL이므로 while문이 실행되지 않는다.

//insertAtTail function
	p -> next = tmp;
	tmp -> prev = p;

insertAtTail 함수가 종료되며,

함수 내의 지역변수는 사라진다.

마지막으로, 다시 main이다.

//main
	insertAtTail(6);

insertAtTail함수에 파라미터 6을 준다.
함수를 한 라인씩 보자.

//insertAtTail function
	Node* p = head;

//insertAtTail function
	Node* tmp = (Node*)malloc(sizeOf(Node));

p는 주소가 400인 첫 노드를 가리키고 첫 노드의 next는 NULL이 아니므로 if문에 진입하지 않는다. (if 문은 아무 노드도 없을 때에 진입하는 것)

//insertAtTail function
	 while(p -> next != NULL){
		 p = p -> next;
	}

p가 가장 마지막 노드인, 주소가 100인 두번째 노드를 가리킨다.

//insertAtTail function
	p -> next = tmp;
	tmp -> prev = p

끝이다.

정리

새로운 노드를 생성하고 (첫 노드를 만들 때를 제외하고는) head를 통해 마지막 노드로 이동한 후, 생성한 노드의 prev와 마지막 노드의 next를 이어주는 흐름으로 이루어진다.