단순연결리스트

ppparkta·2022년 3월 29일

자료구조

목록 보기

2/9

*이 글은 2022년 1월~2월 진행한 스터디를 옮긴 글입니다.

22.01.07 단순연결리스트 복습

선형리스트

차례대로 나열된 자료들의 집합
선형리스트는 배열 / 연결리스트로 구현 가능.

배열vs연결리스트

	배열	연결리스트
장점	구현이 간단하다	-자료의 삽입/삭제가 용이하다. -자료의 절대적인 크기 제약이 없다. -연속된 기억장소를 필요로 하지 않는다.
단점	-자료의 삽입/삭제가 어렵다. -자료의 절대적인 크기를 늘릴수 없다. -자료가 연속해서 저장되므로 연속된 기억장소가 필요하다.	구현이 복잡하다

단순연결리스트 관련 연산

노드의 구조

class *Node{
	public:
		int data; //원하는 구조에 맞춰 데이터 수정
		Node *link; //단 다음 노드와 연결하기 위한 포인터는 반드시 존재
};

노드의 삽입 노드를 삽입하기 위해 고려해야 할 사항을 몇가지 나열하면 다음과 같다. 이 고려사항을 토대로 경우에 맞는 노드삽입 함수를 짰다.

삽입하고자 하는 노드의 선행노드를 아는가? (Y/N)
*헤드포인터가 NULL인가? (Y/N)*
(선행노드를 아는 경우) 선행노드의 link가 NULL인가? (Y/N)

(선행노드를 모르는 경우) 자료를 어디에 추가하는가? (맨 앞/맨 뒤)

👉 **삽입하려는 노드의 선행 노드를 아는 경우**

/*Node*Head=NULL; 전역변수로 선언됨*/
void insert_node_pre(Node *pre,Node* new_node) {
	//1-1. Head포인터가 NULL인 경우
	if (Head == NULL) {
		Head = new_node;
	}
	//1-2. pre->link가 NULL인 경우
	else if{
		new_node->link = Head; //헤드포인터 값을 가져오고
		Head = new_node; //헤드포인터를 자기 자신으로 수정한다
	}
	//1-3. 그 외
	else {
		new_node->link = pre->link;
		pre->link = new_node;
	}
}

👉 **삽입하려는 노드의 선행 노드를 모르는 경우**

**/*리스트의 가장 앞에 노드 삽입*/**
void insert_node_nopre_front(Node *new_node){
	//2. 앞 노드가 주어지지 않은 경우
	//2-1. 노드의 가장 처음에 삽입
	if (Head == NULL) {
		Head = new_node;
	}
	else {
		new_node->link = Head;
		Head = new_node;
	}
}

**/*리스트의 가장 마지막에 노드 삽입*/**
void insert_node_nopre_end(Node*new_node) {
	//2. 앞 노드가 주어지지 않은 경우
	//2-2. 노드의 가장 마지막에 삽입
	**Node* list = Head;**
	if (Head == NULL) {
		Head = new_node;
	}
	else {
		while (list->link != NULL) {
			list = list->link;
			list->link = new_node;
		}
	}
}

노드의 삭제 노드를 삭제할 때도 어떤 방식으로 구현할지에 따라서 몇가지 고려사항을 나열했다. 필요에 따라 리스트의 가장 마지막 노드를 지우는 것도 구현 가능할 것 같다. 연결리스트 삭제 연산에서 중요한 개념은 자료를 완전히 삭제하는 것이 아니라 리스트 간의 연결을 끊는 것이다.
- 삭제하고자 하는 노드의 선행노드를 아는가 ? (Y/N)
- 내가 원하는 특정 값의 데이터만 지우는가? (Y/N)
- *헤드포인터가 NULL인가? (Y/N)*
  👉 **삭제하려는 노드의 선행노드를 아는 경우**
```
**/*앞 노드가 주어진 노드의 삭제*/**
void delete_node(Node* pre) {
	if (Head == NULL) {
		return;
	}
	else if (pre == NULL) {
		Head = Head->link;
	}
	else {
		pre->link = pre->link->link;
	}
}
```
  👉 **특정 값의 데이터만 삭제하려는 경우**
```
**/*특정 데이터값만 삭제하는 경우*/**
void delete_node_key(int key) {
	Node* list = Head;
	while (list->link != NULL) { 
		**if (list->link->data == key)** {
			list->link = list->link->link;
		}
	}
}
```

-22.01.09실제 구현 코드(22.01.10수정)

#include <iostream>
using namespace std;

class Node {
public:
	int data;
	Node *link;
};

Node* Head;

//노드삽입A(선행 노드 이용해서 노드 넣기)
void insert_node(Node *pre, Node *new_node) { //A, B, C
	if (Head == NULL) {
		Head = new_node;
	}
	else if (pre == NULL) {
		new_node->link = Head;
		Head = new_node;
	}
	else {
		new_node->link = pre->link;
		pre->link = new_node;
	}
}
//노드삽입B(리스트 마지막에 노드 넣기)
void insert_node_rear(Node* new_node) {
	if (Head == NULL) {
		Head = new_node;
	}
	else {
		Node* list = Head;
		while (list->link != NULL) {
			list = list->link;
			list->link = new_node;
		}
	}
}
//노드삽입C(리스트 처음에 노드 넣기! 제일 간단)
void insert_node_front(Node *Head,Node *new_node) {
	new_node->link = Head;
	Head = new_node;
}

//data==key인 노드삭제
void deletr_node(int key) {
	Node* list = Head;
	if (Head == NULL)return;
	else if(Head->data==NULL){
		Head = Head->link;
		return;
	}
	else {
		while (list->link != NULL) {
			if (list->link->data == key) {
				list->link = list->link->link;
				return;
			}
		list = list->link;
		}
	}
}

void print_list() {
	for (Node *ptr = Head; ptr != NULL; ptr = ptr->link) {
		cout << ptr->data << endl;
	}
}

void main() {
	Head = NULL;

	for (int i = 0; i < 8; i++) {
		//새로운 데이터 차례로 입력
		int i_data;
		cout << "값 입력: ";
		cin >> i_data;

		//새로운 노드 생성하여 내용 수정
		Node* new_node = new Node;
		new_node->data = i_data;
		new_node->link = NULL;

		//전체 연결리스트에 삽입
		insert_node(NULL, new_node);
	}

	//출력
	print_list();

	//삭제
	for (int i = 0; i < 3; i++) {
		int del_data;
		cout << "삭제할 노드의 값: ";
		cin >> del_data;
		deletr_node(del_data);
	}
	cout << "삭제 후 연결리스트는: \n";
	print_list();
}

ppparkta

겉촉속촉

이전 포스트

배열

다음 포스트