[자료구조] 링크드 리스트 정리 및 구현

[자료구조] 링크드 리스트 정리 및 구현

목차

1. 정리

2. 구현

 

정리

개념

1) 링크드리스트

기본 리스트가 물리적으로 연속된 메모리에 연결되어있는 것과 달리, 각 원소에 저장되어 있는 다음 원소의 주소에 대한 참조에 의해 연결되는 리스트이다.

 

2) 노드

 링크드 리스트에서의 원소는 다음 원소에 대한 주소를 저장해야하기 때문에 <원소, 주소> 단위로 저장되는데 이를 노드라고 한다.

노드

 

 

노드는 원소의 값을 저장하는 데이터 필드와 다음 노드의 주소를 저장하는 링크 필드로 구성된다.  

 

 

종류

1. 단순 링크드 리스트

단순 링크드 리스트

 

노드가 다음 노드와 연결되는 기본적인 링크드 리스트이다. 첫번째 노드를 HEAD, 마지막 노드를 TAIL이라고 한다.

 

 

2. 원형 링크드 리스트

원형 링크드 리스트

 

마지막 노드가 첫번쨰 노드를 가리키게 하여 리스트 구조를 원형으로 만든 것이다. 마지막 노드와 첫번째 노드가 연결되어 있기 때문에 링크를 순회하면서 이전 노드를 접근할 수 있다.

 

 

3. 이중 링크드 리스트

이중 연결 리스트

 

원형 링크드 리스트에서도 현재 노드 바로 직전 노드에 접근하려면  리스트 한바퀴를 순회해야하므로 효율적이지 못하다. 따라서 이부분을 해결하기 위해 이중 링크드 리스트가 등장했다. 직전 노드에 대한 참조를 더해, 양쪽으로 순회할 수 있도록 한 것이 바로 이중 연결리스트이다.

 

 

구현

연결 리스트 구현

#include <iostream>
using namespace std;

// Node 구현
struct Node
{
	int data;
	struct Node* next; // 다음 노드 주소 저장 포인터
};

class LinkedList {
private:
	Node* head;
	Node* tail;

public:
	// 생성자
	LinkedList() {
		// head & tail 초기화
		head = NULL;
		tail = NULL;
	}

	// ==method==

	// 첫번째에 node 추가
	void addFrontNode(int n);

	// 마지막에 node 추가
	void addLastNode(int n);

	// 특정 index에 노드 추가
	void addNode(int index, int data);

	// node 삭제
	void deleteNode(int data);

	// LinkedList 출력
	void print(Node* head);

	// 첫노드 가져오기
	Node* getHead() {
		return head;
	}

};

int main() {
	LinkedList myList;
	myList.addFrontNode(5);
	myList.addFrontNode(7);
	myList.addFrontNode(4);
	myList.addFrontNode(3);
	myList.addFrontNode(4);

	// 삭제
	cout << "==삭제전===\n";
	myList.print(myList.getHead());
	cout << "===========\n\n";
	myList.deleteNode(3);
	myList.deleteNode(4);
	cout << "\n==삭제후===\n";
	myList.print(myList.getHead());
	cout << "===========\n\n";

	// 추가
	myList.addNode(1, 2);
	myList.print(myList.getHead());

	return 0;
}

void LinkedList::addFrontNode(int n)
{
	Node* tmp = new Node;
	//temp의 데이터 n
	tmp->data = n;
	// LinkedList 비어있으면
	if (head == NULL) {
		tmp->next = NULL;
		// 첫번째 노드 = tmp
		head = tmp;
		// 마지막 노드 = tmp
		tail = tmp;
	}
	else {
		// temp의 nextNode는 head
		tmp->next = head;
		// head는 tmp
		head = tmp;
	}
}

void LinkedList::addLastNode(int n)
{
	Node* tmp = new Node;
	tmp->data = n;
	tmp->next = NULL; // tail이 될것이므로
	// LinkedList 비어있으면
	if (head == NULL) {
		head = tmp;
		tail = tmp;
	}
	else {
		// 현재 기준 마지막 node의 next node tmp
		tail->next = tmp;
		//마지막 node는 tmp
		tail = tmp;
	}
}

void LinkedList::addNode(int index, int data) {
	cout <<"명령:  index " << index << "에 "<< data << " 를 추가하자\n";
	// 길이 구하기
	int length = 1;
	Node* lengthCheckNode = head;

	while (lengthCheckNode->next != NULL) {
		length += 1;
		lengthCheckNode = lengthCheckNode->next;
	}
	// index가 길이이상인 경우	
	if (index >= length) {
		cout << "링크드 리스트 길이: " << length << "\nERROR: index가 길이 범위를 벗어납니다.\n";
	}
	// index안에서 가능한 경우
	else {
		Node* previous = head;
		// index의 직전 node 찾기
		for (int i = 0; i < index-1; i++) {
			previous = previous->next;
		}
		// 맨앞에다 추가하는 경우 
		if (index == 0) {
			addFrontNode(data);
		}
		// 그 외
		else {
			Node* inputNode = new Node;
			inputNode->data = data;
			// input노드와 current노드 연결
			inputNode->next = previous->next;
			// 직전 node와 input노드 연결
			previous->next = inputNode;
			
		}
		
	}
}

void LinkedList::deleteNode(int data)
{
	cout <<"명령: " << data << "(을)를 지워보자\n";
	Node* preNode; // 삭제하려는 노드의 이전 노드
	Node* currentNode = NULL;
	preNode = head;
	// 이전 노드 구하기
	// 1. 지우려는 노드가 head인 경우
	if (preNode->data == data) {
		currentNode = preNode;
		if (head->next == NULL) {
			cout << "노드가 1개라 지울 수 없습니다.\n";
		}
		else {
			Node* nextNode = head->next;
			head = nextNode;
			delete currentNode;
		}

	}
	// 2. 그외
	else {
		while (preNode->next != NULL and preNode->next->data != data) {
			preNode = preNode->next;
		}
		currentNode = preNode->next;

		// 지우려는 노드가 끝인경우
		if (currentNode->next == NULL) {
			preNode->next = NULL;
			tail = preNode;
			delete currentNode;
		}
		// 중간인 경우
		else {
			Node* nextNode = currentNode->next;
			preNode->next = nextNode;
		}
	}
}

void LinkedList::print(Node* head)
{
	if (head == NULL) {
		cout << "\n";
	}
	else {
		cout << head->data << " ";
		print(head->next);
	}
}