본문 바로가기

자료구조

단순 연결 리스트(Single linked list)

연결리스트는 노드들이 모여서 다음 데이터를 가리키는 형태로 구성되어 있다. 각각의 노드는 노드가 가지고 있는 데이터와 다음 노드를 가리키는 포인터가 모여서 구성된다. 

단순 연결 리스트의 구성

배열과 달리 연결리스트는 인덱스가 없기 때문에 삽입과 삭제를 위해 원하는 위치까지 노드를 이동해야 된다. 또한 배열과 다르게 자료형의 주소가 순차적이 아니라 임의의 주소로 정해진다. 리스트를 탐색하는 경우에도 원하는 값을 찾을 때 까지 노드를 이동해야 한다.

 

단순 연결리스트는 노드의 이동이 한쪽 방향으로 일어나는 리스트이다.

 

다음은 단순 연결 리스트를 구현할 때 필요한 함수들이다.

  • insert : 노드를 추가하는 함수, 맨 앞에 노드를 추가하는 경우는 새로 추가한 노드가 head 노드가 되게 하고 원래 자리에 있던 노드를 새로 만든 노드에 연결, 중간에 노드를 추가하는 경우는 전에 연결되어 있던 노드를 새로 만든 노드 다음에 연결 시킨 후 삽입하려는 바로 앞자리에 새로 만든 노드를 연결, 마지막에 노드를 추가하는 경우는 맨 마지막 노드 뒤에 새로 만든 노드를 추가
  • delete : 노드를 삭제하는 함수, 맨 앞에 노드를 삭제하는 경우는 두번째 노드를 head 노드에 넣어주고 맨 앞에 노드를 삭제, 중간에 노드를 삭제하는 경우는 내가 삭제하고 싶은 바로 이전 자리에 노드가 삭제하고 싶은 노드 바로 다음 노드를 가리키게 한 후 내가 삭제하고 싶은 노드를 삭제, 마지막 노드를 삭제하는 경우는 단순하게 마지막 노드를 삭제
  • size : 노드가 총 몇 개 있는지 반환하는 함수
  • show : 노드의 data를 출력해주는 함수, 마지막 노드를 만날 때까지 순회
  • find : 입력한 data에 해당하는 노드를 찾는 함수, 원하는 값을 만날 때 까지 노드를 순회, 여기서는 같은 데이터가 있으면 맨 앞에 노드를 반환해주도록 구현

c++로 단순 연결 리스트를 구현하면 다음과 같다.

#include <iostream>
using namespace std;

//노드 클래스
class Node {
public:
	int data; //노드가 가지고 있는 값
	Node* ptr; //다음 노드를 가리키는 포인터

	//생성자
	Node() {
		data = 0;
		ptr = NULL;
	}
};

//리스트 클래스
class List {
public:
	int cnt; //노드의 갯수
	Node* head; //첫번째 노드를 가리키는 포인터

	//생성자
	List() {
		cnt = 0;
		head = NULL;
	}

	void insertNode(int where, int data); //원하는 곳에 노드를 삽인하는 함수
	void deleteNode(int where); //원하는 곳에 노드를 삭제하는 함수
	int size(); //현재 원소의 갯수
	bool findNode(int data, int& node); //원하는 값을 찾는 함수, 참조를 이용하여 삭제한 노드의 data를 반환한다.
	void show(); //리스트의 원소들을 출력
};



//원하는 곳에 노드를 삽인하는 함수
void List::insertNode(int where, int data) {
	int loop = 1; //노드를 찾을 때 몇 번째 노드인지 세어줄 변수
	Node* newNode = new Node[1]; //노드 생성
	Node* temp = head; //임시로 저장할 노드가 있을 때 사용할 변수, 처음은 첫번째 노드를 넣는다.
	newNode->data = data;
	if (cnt == 0) { //노드는 없을 때 어떤 수가 들어와도 노드의 첫번째로 노드를 넣어준다.
		head = newNode;
		cnt++;
		return;
	}
	if (where == 1) { //첫번째 노드로 새로 만든 노드를 넣는 경우
		head = newNode; //첫번째 노드를 새로운 노드로 넣는다.
		newNode->ptr = temp; //새로운 노드 다음노드에 이전에 담아놓았던 노드를 넣는다.
	}
	else { //첫번째를 제외한 자리에 새로 만든 노드를 넣는 경우
		if (cnt < where) { //맨 끝에 노드로 추가하는 경우
			where = cnt + 1; //항상 노드의 갯수보다 하나 더 크게 위치를 잡는다.
		}
		while (loop != where - 1) { //삽입할 노드 바로 다음에 들어가야하기 때문에 
			temp = temp->ptr; //다음 노드로 이동
			loop++; //루프 증가
		}
		newNode->ptr = temp->ptr; //원래 삽입하려는 자리에 있는 노드를 현재 새로 생성한 노드의 다음 값으로 삽입
		temp->ptr = newNode; //원래 삽입하려는 위치에 추가
	}
	cnt++; //노드 갯수 증가
}

//원하는 곳에 노드를 삭제하는 함수, 참조를 이용하여 삭제한 노드의 data를 반환한다.
void List::deleteNode(int where) {
	if (cnt == 0 || cnt < where) { //노드의 개수가 0이거나 노드의 갯수보다 큰 숫자가 입력된 경우
		cout << "삭제할 노드가 없습니다.\n";
		return;
	}
	int loop = 1; //몇번째 노드인지 세어줄 변수
	Node* temp = head; //지울 노드를 담아놓을 변수, 우선 첫번째 노드를 담아 놓는다.
	if (where == 1) { //첫번째 노드를 삭제하는 경우
		head = head->ptr; //첫번째 노드 다음 노드를 첫번째 노드로 설정
		delete temp;
	}
	else { //첫번째 이외에 노드를 삭제하는 경우
		while (loop != where - 1) { //삭제하기 직전의 노드를 찾는다.
			temp = temp->ptr;
			loop++;
		}
		if (temp->ptr == NULL) { //마지막 노드인 경우
			temp = temp->ptr; //삭제하기전 바로 직전 노드가 가리키는 값이 NULL이 되게 만든다.
			delete temp; //삭제할 노드를 delete로 삭제
		}
		else { //마지막 노드가 아닌 경우
			Node* erase = temp->ptr; //삭제할 노드로 노드를 옮긴다.
			temp->ptr = temp->ptr->ptr; //삭제하기전 노드에 삭제할 노드의 바로 다음 노드를 넣는다.
		}
	}
	cnt--;
}

int List::size() { //현재 원소의 갯수
	return cnt;
}


bool List::findNode(int data, int& node) { //원하는 값을 찾는 함수, 여러 개의 값이 있으면 제일 처음 값을 찾는다.
	int cnt = 1;
	Node* temp = head; //제일 첫번째 노드를 head노드로 설정
	while (temp) {
		if (temp->data == data) { //찾는 노드의 data가 입력한 data와 같으면
			node = cnt;
			return true; //노드를 찾으면 true 반환
		}
		temp = temp->ptr; //다음 노드로 이동
		cnt++; //노드의 위치 증가
	}
	return false; //못찾는 경우 false 반환
} 

void List::show() { //리스트의 원소들을 출력
	Node *temp = head; //시작은 처음 노드로 정한다.
	cout << "시작 : ";
	while (temp) {
		cout << temp->data; //노드의 data 출력
		cout << ' ';
		temp=temp->ptr; //다음 노드로 이동
	}
	cout << '\n';
}

int main() {
	List* list = new List;
	while (1) {
		int what;
		int where, n; //원하는 곳을 나타내는 변수와 원하는 데이터를 넣는 변수
		int node; //노드의 위치를 나타내는 변수
		cout << "1. 삽입, 2. 삭제, 3. 노드 찾기, 4. 전체 원소 출력, 5. 노드의 갯수, 6.종료 : "; cin >> what;
		switch (what) {
		case 1:
			cout << "원하는 위치와 값 입력 : ";  cin >> where >> n;
			list->insertNode(where, n);
			break;
		case 2:
			cout << "삭제하기 원하는 위치 입력 : "; cin >> where;
			list->deleteNode(where);
			break;
		case 3:
			cout << "찾기 원하는 data : "; cin >> n;
			if (list->findNode(n, node)) {
				cout << node << "번째의 존재합니다.\n";
			}
			else {
				cout << "존재하지 않는 data입니다.\n";
			}
			break;
		case 4:
			list->show();
			break;
		case 5:
			cout << list->size() << "개 있습니다.\n";
			break;
		case 6:
			return 0;
		}
		cout << "\n\n";
	}
}

'자료구조' 카테고리의 다른 글

트리(이진트리순회)  (0) 2019.08.02
큐(Queue)  (0) 2019.07.14
스택(Stack)  (0) 2019.07.05