선형 자료구조 정리 (연결리스트)

연결리스트(Linked List) 란?

1. 연결리스트는 동적으로 크기를 조절(동적할당)하므로 배열을 사용하는것 보다 메모리를 효율적으로 사용 할 수 있다.

2. 일반적으로 배열이나 배열 큐, 스택을 사용할때, 배열 중간에 데이터를 삽입하기 위해서는 처음이나 끝에서 차례차례 이동시켜야하기 때문에 불필요한 연산을 많이 하게된다. 이 때 이러한 Sequential 표현에서 데이터 이동의 문제점을 해결할 수 있는 방법이 바로 연결리스트이다.

 

[그림 1] 연결리스트(Linked List) 구조

단순 연결 리스트에서는 데이터를 가지고 있는 공간인 Node와 그 다음 주소를 저장하는 공간인 next Node로 구성되어있고, Node의 마지막 데이터 공간의 nest Node에는 Null 값이 들어간다.

 

Node = 데이터 값을 가지고 있는 공간

next Node = 다음 데이터의 주소를 저장하는 공간

 

연결리스트 장점

1. 연결리스트를 사용하게 되면, 연속된 리스트에 데이터들이 일정한 거리만큼 떨어져서 저장되는 것과 달리 데이터가 메모리 내의 어느 공간에서나 위치 할 수 있다.

2. 저장과 수정이 간단하기 때문에 데이터의 수를 정확하게 예측할 수 없거나, 데이터의 갯수가 계속해서 바뀌는 경우에 연결리스트를 사용하면 좋다.

 

연결리스트 단점

연결리스트는 Node에 저장되어 있는 nextNode를 따라서 다음 저장된 값을 찾기 때문에 원하는 값의 위치를 찾기 위해서는 처음부터 순차적으로 탐색해야하는 단점이 있다.

head->nextNode->nextNode //세번째 노드 탐색

 

연결리스트 알고리즘 : 앞의 데이터 추가하기

[그림 2] 연결리스트 앞의 데이터 추가

//첫번째의 node 추가
void addFrontNode(int n) {
	node* temp = new node;
	//temp의 데이터는 n
	temp->data = n;

	//LinkedList가 비어있으면
	if (head == NULL) {
		//첫 node는 temp
		head = temp;
		//마지막 node는 temp
		tail = temp;
	}
	//LinkedList에 데이터가 있으면
	else {
		//temp의 nextNode는 head
		temp->nextNode = head;
		//head는 temp
		head = temp;
	}
}

 

연결리스트 알고리즘 : 마지막에 데이터 추가하기

[그림 3] 연결리스트 마지막에 데이터 추가

//마지막의 node 추가
void addNode(int n) {
	node* temp = new node;

	//temp의 데이터는 n
	temp->data = n;
	//temp의 nextNode = NULL값
	temp->nextNode = NULL;

	//LinkedList가 비어있으면
	if (head == NULL) {
		//첫 node는 temp
		head = temp;
		//마지막 node는 temp
		tail = temp;
	}
	//LinkedList에 데이터가 있으면
	else {
		//현재 마지막 node의 nextNode는 temp
		tail->nextNode = temp;
		//마지막 node는 temp
		tail = temp;
	}
}

 

연결리스트 알고리즘 : 데이터 삽입하기

[그림 4] 연결리스트 데이터 삽입하기

//node 삽입
void insertNode(node* prevNode,int n) {
	node* temp = new node;
	//temp의 데이터는 n
	temp->data = n;

	//temp의 nextNode 저장
	//(삽입 할 앞 node의 nextNode를 temp의 nextNode에 저장)
	temp->nextNode = prevNode->nextNode;
	
	//temp 삽입
	//temp앞의 node의 nextNode를 temp로 저장
	prevNode->nextNode = temp;
}

 

연결리스트 알고리즘 : 데이터 삭제하기

[그림 5] 연결리스트 데이터 삭제하기

//node 삭제
void deleteNode(node* prevNode) {

	//삭제할 node를 temp에 저장
	//(삭제할 node의 1단계 전 node의 nextNode) 
	node* temp = prevNode->nextNode;

	//삭제할 node를 제외
	//(삭제할 node의 nextNode를 1단계 전 node의 nextNode에 저장)
	prevNode->nextNode = temp->nextNode;

	//temp 삭제
	delete temp;
}

 

연결리스트 : 데이터 출력하기

void display(node* head) {
	if (head == NULL) {
		cout << "비었습니다.\n";
	}
	else {
		cout << head->data << endl;
		display(head->nextNode);
	}
}

 

연결리스트 전체 소스코드

#include <iostream>

using namespace std;

//노드 struct 구현 (data값과 nextNode가 존재)
struct node {
	int data;
	node* nextNode;
};

//링크드 리스트 클래스 생성
class LinkedList {
private:
	node* head;
	node* tail;
public:
	LinkedList() {
		//head 와 tail의 포인터를 초기화;
		head = NULL;
		tail = NULL;
	}
	//첫번째의 node 추가
	void addFrontNode(int n);
	//마지막의 node 추가
	void addNode(int n);

	//node 삽입
	void insertNode(node* prevNode, int n);
	//node 삭제
	void deleteNode(node* prevNode);

	//첫번째 노드 가져오기
	node* getHead() {
		return head;
	}
	//LinkedList 출력
	void display(node* head);
};

//첫번째의 node 추가
void LinkedList::addFrontNode(int n) {
	node* temp = new node;
	//temp의 데이터는 n
	temp->data = n;

	//LinkedList가 비어있으면
	if (head == NULL) {
		//첫 node는 temp
		head = temp;
		//마지막 node는 temp
		tail = temp;
	}
	//LinkedList에 데이터가 있으면
	else {
		//temp의 nextNode는 head
		temp->nextNode = head;
		//head는 temp
		head = temp;
	}
}

//마지막의 node 추가
void LinkedList::addNode(int n) {
	node* temp = new node;

	//temp의 데이터는 n
	temp->data = n;
	//temp의 nextNode = NULL값
	temp->nextNode = NULL;

	//LinkedList가 비어있으면
	if (head == NULL) {
		//첫 node는 temp
		head = temp;
		//마지막 node는 temp
		tail = temp;
	}
	//LinkedList에 데이터가 있으면
	else {
		//현재 마지막 node의 nextNode는 temp
		tail->nextNode = temp;
		//마지막 node는 temp
		tail = temp;
	}
}

//node 삽입
void LinkedList::insertNode(node* prevNode,int n) {
	node* temp = new node;
	//temp의 데이터는 n
	temp->data = n;

	//temp의 nextNode 저장
	//(삽입 할 앞 node의 nextNode를 temp의 nextNode에 저장)
	temp->nextNode = prevNode->nextNode;
	
	//temp 삽입
	//temp앞의 node의 nextNode를 temp로 저장
	prevNode->nextNode = temp;
}

//node 삭제
void LinkedList::deleteNode(node* prevNode) {

	//삭제할 node를 temp에 저장
	//(삭제할 node의 1단계 전 node의 nextNode) 
	node* temp = prevNode->nextNode;

	//삭제할 node를 제외
	//(삭제할 node의 nextNode를 1단계 전 node의 nextNode에 저장)
	prevNode->nextNode = temp->nextNode;

	//temp 삭제
	delete temp;
}

//LinkedList 출력
void LinkedList::display(node* head) {
	if (head == NULL) {
		cout << "\n";
	}
	else {
		cout << head->data << " ";
		display(head->nextNode);
	}
	cout << endl;
}



//메인 함수
int main() {
	LinkedList a;
	//1추가
	a.addNode(1);
	//2추가
	a.addNode(2);
	//3추가
	a.addNode(3);

	//display
	cout << "1,2,3을 LinkedList에 추가\n";
	a.display(a.getHead());

	//0을 제일 앞에 추가
	a.addFrontNode(0);

	//1을 네번째에 추가
	a.insertNode(a.getHead()->nextNode->nextNode, 1);
	cout << "0을 첫번째에 추가, 1을 네번째에 추가\n";
	a.display(a.getHead());

	//세번째 노드 삭제
	a.deleteNode(a.getHead()->nextNode);

	//display
	cout << "세번째 노드를 삭제\n"; 
	a.display(a.getHead());

}