[자료구조] 연결리스트 - 삽입과 삭제, 순회

 

1. 삽입

 1. 가장 앞에 삽입하는 경우

 

 

    - 새 노드를 만들어 추가할 데이터를 저장한다.

    - 새 노드의 next 필드가 현재의 head 노드를 가리키도록 한다.

    - 새 노드를 새로운 head로 한다. 

 

Node *tmp = (Node*)malloc(sizeof(Node));
tmp->data = "Ann";
tmp->next = head;
head = tmp;

 

 

2. 중간에 삽입하는 경우

 

    - 새 노드를 만들어 추가할 데이터를 저장한다.

    - 새 노드의 next 필드가 prev의 다음 노드를 가리키도록 한다.

    - 새 노드를 prev의 다음 노드로 만든다.

 

Node *tmp = (Node*)malloc(sizeof(Node));
tmp->data = "Jim";
tmp->next = prev->next;
prev->next = tmp;

 

---

 

 

2. 삭제

 

 1. 가장 앞의 노드를 삭제하는 경우

 

    - head가 현재 head 노드의 다음 노드를 가리키게 만든다.

 

if (head == NULL)
	return NULL;
    
else {
	Node *tmp = head;
	head = head->next;
	return tmp;
}

 

 

 2. 중간 노드를 삭제하는 경우

 

 

    - prev의 다음 노드가 NULL이 아니라면 prev의 next 필드가 현재 next 노드의 다음 노드를 가리키게 만든다.

 

Node *tmp = prev->next;
if (tmp == NULL)
	return NULL;
    
else {
	prev->next = tmp->next;
	return tmp;
}

 

---

 

3. 순회

 

    - 연결리스트의 노드들을 처음부터 순서대로 방문한다.

    - 문자열 word와 동일한 단어를 가진 노드를 찾아 주소를 반환한다.

 

Node *p = head;
while (p != NULL) {
	if (strcmp(p->data, word) == 0)
		return p;
	p = p->next;
}
return NULL;