저번 시간에는 연결 리스트의 개념에 대해서 배웠다.
이번 포스팅에서는 실질적으로 연결리스트를 어떻게 구현하는지!에 대해서 소개하고자 한다.
🧱구조
- 헤드 노드(Head)
- 일반 노드들
- 테일 노드(Tail)
헤드 노드와 테일 노드는 리스트의 시작과 끝을 나타내는 노드들이다.
헤드 노드와 테일 노드에는 데이터를 저장하지 않으며, 헤드 노드의 경우, 링크 부분에 다음 데이터의 주소를 저장하고 있다.
💻 코드
노드
struct node{
int data;
node* nextNode;
};구조체로 노드를 표현하였다.
데이터 data 와 다음 노드의 주소 nextNode (링크)를 구조체의 멤버로 가지고 있다.
LinkedList 클래스 초기화
class LinkedList{
private:
node* head = new node;
node* tail = new node;
public:
LinkedList(){
head->nextNode = tail;
tail->nextNode = NULL;
}
}
LinkedList 클래스를 만들었다.
멤버 변수로 head와 tail 노드를 두었고, 생성자에서 두 노드를 초기화하였다. head 노드의 다음 노드 주소로 tail노드를 설정하여 아래 그림과 같은 구조로 초기화하였다.
insert 연산
저번 글에서 설명했다시피, 삽입 연산은 그림처럼,새로 할당한 노드의 주소를 앞 노드에게 알려주고, 새로 할당한 노드의 링크는 원래 앞 노드에 연결되어있던 노드의 주소로 바꾸어 준다고 하였다.
이러한 성질을 이용해 총 세 가지의 삽입 함수를 만들어 보았다.
기본적인 원리는 동일하다!
연결리스트 맨 앞에 노드 추가
// 연결 리스트 맨 앞에 노드 추가
void addFront(int data){
node* newNode = new node;
newNode->data = data;
// 노드가 한개도 없는 경우
if(head->nextNode == tail){
head->nextNode = newNode;
newNode->nextNode = tail;
}
else{ // 노드가 한개 이상인 경우
newNode->nextNode = head->nextNode;
head->nextNode = newNode;
}
}
우선 새로운 노드를 생성한다.
만약 노드가 하나도 없는 경우, 즉 head 노드가 tail노드에 연결되어있는 경우라면, head 노드에 새로운 노드 newNode를 연결하고, newNode의 꽁무니에는 tail노드를 연결해준다.
노드가 하나 이상이라면, 기존에 head에 연결되어있던 노드를 newNode에 연결해준다. 그리고 head의 꽁무니에 newNode를 연결해준다.
연결 리스트 맨 뒤에 노드 추가
void pushBack(int data){
// 노드가 한개도 없는 경우
if(head->nextNode == NULL){
addFront(data);
}
// 노드가 한개 이상인 경우
else{
// 새로운 노드 생성
node* newNode = new node;
newNode->data = data;
// 마지막 노드 찾기
node* curNode = head->nextNode;
while(curNode->nextNode!=tail){
curNode = curNode->nextNode;
}
// tail 노드 앞에 삽입
curNode->nextNode = newNode;
newNode->nextNode = tail;
}
}노드가 하나도 없는 경우에는 맨 앞에 노드를 추가하는 것이나 맨 뒤에 추가하는 것이나 동일하다. 따라서 addFront 함수를 호출하여 노드를 삽입하였다.
노드가 하나 이상인 경우에는 기존에 tail노드의 앞에 있는 노드를 찾아야 한다.
현재 연결 리스트 구조상, 앞에 있는 노드는 뒷노드의 주소를 알고 있지만, 뒷 노드는 앞의 노드 주소를 알지 못한다.
따라서, while문으로 리스트를 쭉 조회하며 tail 노드의 앞에 있는 노드 즉, 마지막 노드를 찾아야 한다.
마지막 노드를 찾았다면, 마지막 노드 와 tail 노드 사이에 newNode 를 삽입해준다.
특정 주소에 노드 삽입
void insertNode(node* prevNode, int data){
if(prevNode==nullptr){
cout << "올바른 노드주소가 아닙니다. 데이터를 삽입할 수 없습니다.\n";
return;
}
node* newNode = new node;
newNode->data = data;
// prevNode가 맨 마지막에 있는 노드인 경우
if(prevNode->nextNode == tail){
prevNode->nextNode = newNode;
newNode->nextNode = tail;
return;
}
// prevNode가 맨 마지막 노드가 아닌 경우
newNode->nextNode = prevNode->nextNode;
prevNode->nextNode = newNode;
}
insertNode 함수는 prevNode의 뒤에 새로운 노드를 삽입하는 함수이다. 노드 주소가 nullptr일 때는 예외처리를 해주었다.
인자로 들어온 prevNode가 맨 마지막 노드일 경우, newNode 의 뒷 노드로 tail을 연결해주었고, 맨 마지막 노드가 아닌 경우 prevNode와 prevNode의 뒷노드 사이에 newNode를 삽입해주었다.
delete 연산
delete 연산은, 위 그림과 같이, 지우려고 하는 노드의 앞, 뒤에 있는 노드를 서로 연결해주는 방식이다.
void deleteNode(int data){
node* targetNode;
// 빈 리스트인 경우
if(head->nextNode==tail){
cout<<"빈 리스트 입니다."<<endl;
return;
}
// 첫번째 노드가 지우려는 노드일 때
if(head->nextNode->data == data){
targetNode = head->nextNode;
head->nextNode = targetNode->nextNode;
targetNode= nullptr;
delete targetNode;
return;
}
// 지우려는 데이터의 이전 노드 찾기
node* prevNode = head->nextNode;
while(prevNode->nextNode!=tail){
if(prevNode->nextNode->data == data){
targetNode =prevNode->nextNode;
break;
}
prevNode= prevNode->nextNode;
}
// 지우려는 노드를 못찾은 경우
if(prevNode->nextNode==tail){
cout<< "해당 데이터는 존재하지 않습니다.\n";
targetNode= nullptr;
return;
}
// 지우려는 노드는 찾은 경우
if(targetNode->nextNode == tail){ // 현재 노드가 마지막 노드인 경우
prevNode->nextNode = tail;
}else{ // 현재노드가 마지막 노드가 아닌 경우
prevNode->nextNode = targetNode->nextNode;
}
// 지우려는 노드 메모리 해제
targetNode->nextNode= nullptr;
targetNode= nullptr;
delete targetNode;
}
나는 인자로 들어온 data와 같은 값을 가지는 노드를 제거하는 방식으로 구현하였다.
우선, 연결리스트가 비어있는 경우 예외 처리를 해주었고, 첫번째 노드가 지우려는 노드인 경우와 그렇지 않은 경우를 나누어 처리하였다.
-
첫번째 노드가 지우려는 노드인 경우, 즉
head에 바로 연결되어있는 노드가 지우려는 노드targetNode인 경우,targetNode의 뒷노드를head노드와 연결한 후,targetNode의 메모리를 해제해 주었다. -
targetNode가 첫번째 노드가 아닌 경우, 리스트를while문으로 조회하며 인자로 들어온data값을 갖는 노드를 찾았다. -
찾는 노드가 없는 경우는 예외처리 하였다.
-
찾는 노드가 있는 경우,
targetNode의앞노드와뒷노드를 연결해주는 방식으로 처리하였다.
find 연산
추가적으로 원하는 노드의 주소를 반환해주는 find연산을 구현해보았다.
node* findNode(int data){
node* curNode = head->nextNode;
while(curNode->nextNode != NULL){
if(curNode->data == data ){
return curNode;
}
curNode = curNode->nextNode;
}
return nullptr;
}리스트를 처음부터 조회하며 , 인자로 들어온 data값과 같은 값을 가지는 노드 주소를 반환하도록 구현하였고, 일치하는 노드가 없는 경우 nullptr를 반환하였다.
showAll()
// 리스트의 모든 데이터 출력
void showAll(){
if(head->nextNode==tail){
cout << "빈 리스트입니다." << endl;
return;
}
// 첫 노드부터 모든 데이터 조회
node* curNode= head->nextNode;
while(true){
cout << curNode->data;
if(curNode->nextNode == tail){
break;
}
else{
cout <<"-";
curNode = curNode->nextNode;
}
}
cout<<endl;
}마지막으로, 리스트 삽입, 삭제가 정상적으로 이루어졌는지 확인하기 위해, 리스트에 있는 모든 노드의 데이터를 출력하는 함수를 만들었다.
결과
아래와 같이 메인 함수를 작성해보았다.
int main()
{
LinkedList linkedList = LinkedList();
linkedList.showAll();
// addFront 예제
linkedList.addFront(3);
linkedList.showAll();
linkedList.addFront(2);
linkedList.showAll();
linkedList.addFront(1);
linkedList.showAll();
// pushBack 예제
linkedList.pushBack(4);
linkedList.showAll();
linkedList.pushBack(5);
linkedList.showAll();
// findNode
node* curNode = linkedList.findNode(5);
// insert 예제
if(curNode!=0){
linkedList.insertNode(curNode,6);
linkedList.showAll();
}
// deleteNode 예제
linkedList.deleteNode(1);
linkedList.showAll();
linkedList.deleteNode(6);
linkedList.showAll();
linkedList.deleteNode(5);
linkedList.showAll();
return 0;
}출력 결과
빈 리스트입니다.
3
2-3
1-2-3
1-2-3-4
1-2-3-4-5
1-2-3-4-5-6
2-3-4-5-6
2-3-4-5
2-3-4
📕 정리
이번 글에서는 연결 리스트를 직접 코드로 구현해보았다.
사실 실제 알고리즘 문제를 풀 때는 C++ 에서 제공하는 라이브러리를 사용하면 되기 때문에, 이렇게 실제로 구현할 일은 많이 없을 것이다.
그래도 이렇게 해보는 이유는 개념을 정확히 이해하기 위해서! 라고 할 수 있다.
그리고 사실 개인적인 이유도 있는데, 1학년 수업을 들을 때 제대로 이해도 안하고 얼렁뚱땅 교수님이 하시는 대로 연결 리스트 따라서 구현했다가.. 잘못 따라쳐서 제대로 작동을 안한 기억이 강하게 남아있어 연결 리스트가 왠지 자신이 없었다. 그 이후로 그냥 라이브러리 쓰고~ 이랬는데, 아 왠지 양심에(?) 너무 찔려서 리벤지를 해야겠더라.
그래서 지금에서야 복수 완료...ㅎㅎ ^.^
그래도 뭔가 아쉬우니까 다음 포스팅에서는 연결리스트 라이브러리 사용하는 방식을 설명해보겠다. 이것까지 정리하면 연결 리스트 완전 정복~?
전체 코드는 링크를 참고해주세요😊
