[자료구조][c++] 연결 리스트 Linked List

연결리스트(Linked List)란?

 

연결 리스트, 링크드 리스트(linked list)는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조이다. 이름에서 말하듯이 데이터를 담고 있는 노드들이 연결되어 있는데, 노드의 포인터가 다음이나 이전의 노드와의 연결을 담당하게 된다.

연결 리스트는 늘어선 노드의 중간지점에서도 자료의 추가와 삭제가 O(1)의 시간에 가능하다는 장점을 갖는다. 그러나 배열이나 트리 구조와는 달리 특정 위치의 데이터를 검색해 내는데에는 O(n)의 시간이 걸리는 단점도 갖고 있다.

 

C++ 코드를 통해 연결리스트를 간단히 구현해보겠습니다.

 

---

간단하게 구현한 연결리스트 METHOD (삽입,삭제,조회)

 

insert(head, data)

리스트 head의 맨 뒤 노드에 data를 삽입합니다.

getData(head, index)

리스트 head로부터 index 만큼 떨어진 노드에 저장된 데이터를 반환합니다. 인덱스가 범위를 넘어가면 -1을 반환합니다.

remove(head, index)

리스트 head로부터 index 만큼 떨어진 노드를 삭제합니다. 인덱스가 범위를 넘어가면 아무런 수행도 하지 않습니다.

---

구현

 

사용할 구조체

struct Node{
	int data;
	Node* nextNode; // 다음 노드
	Node* prevNode; // 이전 노드
	Node* last; // 마지막 노드
};

 

연결리스트가 제공하는 METHOD들

Node* init(Node* temp){ // 초기화
	temp= new Node();
	temp->nextNode = NULL;
	temp->prevNode = NULL;
	temp->data = 0;
	return temp;
}

Node* insert(Node* head, int data){
	if(head==NULL){// 첫번째 삽입인 경우 
		head=init(head);
		head->data=data;
		head->last=head;
		return head;
	}

	Node* currentNode=head->last;
	Node* newNode=NULL;
	newNode = init(newNode);
	newNode->data=data;
	newNode->prevNode=currentNode;
	currentNode->nextNode=newNode;
	head->last=newNode;
	return head;
}

int getData(Node* head, int index){
	Node* currentNode = head;
	for(int i=0; i<index && currentNode != NULL; i++){
		currentNode=currentNode->nextNode;
	}
	if(currentNode==NULL){
		return -1;//size를 넘겼을 경우 
	}
	return currentNode->data;
}

Node* remove(Node* head, int index){//index번째 노드 삭제 
	Node* currentNode = head;
	Node* prevNode=NULL;//이전 노드
	for(int i=0; i<index && currentNode!=NULL; i++){
		prevNode = currentNode;
		currentNode=currentNode->nextNode;
		if(currentNode == NULL){//인덱스가 사이즈를 넘겼을 경우
			return head;
		}
		if(prevNode==NULL){// 루트 노드를 삭제하는 경우
			head->nextNode->last=head->last;
			head=head->nextNode;
		}
		if(currentNode->nextNode==NULL){//마지막 노드 삭제
			head->last = prevNode;
			prevNode->nextNode=NULL;
		}
		prevNode -> nextNode = currentNode->nextNode;
		currentNode->nextNode->prevNode=prevNode;
		return head;
	}
}

 

전체코드

#include <iostream>
using namespace std;

struct Node{
	int data;
	Node* nextNode; // 다음 노드
	Node* prevNode; // 이전 노드
	Node* last; // 마지막 노드
};

Node* init(Node* temp){ // 초기화
	temp= new Node();
	temp->nextNode = NULL;
	temp->prevNode = NULL;
	temp->data = 0;
	return temp;
}

Node* insert(Node* head, int data){
	if(head==NULL){// 첫번째 삽입인 경우 
		head=init(head);
		head->data=data;
		head->last=head;
		return head;
	}

	Node* currentNode=head->last;
	Node* newNode=NULL;
	newNode = init(newNode);
	newNode->data=data;
	newNode->prevNode=currentNode;
	currentNode->nextNode=newNode;
	head->last=newNode;
	return head;
}

int getData(Node* head, int index){
	Node* currentNode = head;
	for(int i=0; i<index && currentNode != NULL; i++){
		currentNode=currentNode->nextNode;
	}
	if(currentNode==NULL){
		return -1;//size를 넘겼을 경우 
	}
	return currentNode->data;
}

Node* remove(Node* head, int index){//index번째 노드 삭제 
	Node* currentNode = head;
	Node* prevNode=NULL;//이전 노드
	for(int i=0; i<index && currentNode!=NULL; i++){
		prevNode = currentNode;
		currentNode=currentNode->nextNode;
		if(currentNode == NULL){//인덱스가 사이즈를 넘겼을 경우
			return head;
		}
		if(prevNode==NULL){// 루트 노드를 삭제하는 경우
			head->nextNode->last=head->last;
			head=head->nextNode;
		}
		if(currentNode->nextNode==NULL){//마지막 노드 삭제
			head->last = prevNode;
			prevNode->nextNode=NULL;
		}
		prevNode -> nextNode = currentNode->nextNode;
		currentNode->nextNode->prevNode=prevNode;
		return head;
	}
}

void print(Node* currentNode){ // 출력
	while(currentNode!=NULL){
		cout << currentNode->data << " ";
		currentNode=currentNode->nextNode;
	}
	cout<<endl;
	return;
}

int main(){
	Node* list = NULL;
	list=insert(list,1);
	list=insert(list,2);
	list=insert(list,3);
	list=insert(list,4);
	list=insert(list,5);
	list=insert(list,6);
	list=insert(list,7);
	list=insert(list,8);

	print(list);

	list=remove(list,3);
	print(list);
	list=insert(list,700);
	print(list);
}

출력 결과