C++ - 쉽게 설명한 링크드리스트(Linked list) 이야기

링크드리스트(연결리스트) 종결자가 되어봅시다. 

저는 어찌어찌나 봐도 한 개도 이해가 안가던지 '딴 애들은 이걸 어떻게 이해하는 것인가, 나는 과연 이 진로를 계속 가야하나' 진지하게 고민했던 기억이 있답니다

우리가 배열로 리스트를 하나 만든다고 가정해 봅니다. 그것을 관리하기 위한 함수로 대략 이러한 코드가 하나 들어가게 될 것 입니다. 

void ArrayList::insertFirstNode(int data)                        //첫번째 노드에 데이터를 넣어주고 나머지는 한칸씩 밀려나가는 함수

{

if(!is_full())                                                         //어딘가에 이런것도 하나 구현해 두겠죠. 배열이 다 찼다면 애당초 작업하지 않도록

{

for(int i=length-1; i>=0; i--) list[i+1] = list[i];    //자료가 지워지지 않도록 뒤에서부터 들어가네요

list[0]=data;                                                //int 데이터를 넣구요

cout<<"추가됨(처음) : "<<list[0]<<endl;

length++;                                                    //현재 몇 개 방이 차있는지 따로 저장하는 변수인가보군요

}

printList();                                                              //출력함수

}

배열은가 일반적으로 많이 쓰이죠. 코딩도 직관적이고. 인덱스가 되어 있으니 주소 찾아가기도 쉽고..

하지만 위 코드에서 임의의 데이터 999999999개 이상의 배열 앞에 어떤 값이 수시로 추가 되는 상황이 주어진다고 가정해 봅시다, 기존 값들이한 칸,  한 칸씩 밀리는 동안 로딩도 길어질지도 모르고, 쓰지 않을 빈 배열이 메모리를 차지한다거나, 혹은 더 이상 빈 배열이 없어 배열을 재 생성해야 하는 구조가 찝집하기 그지 없다면.. 비로소 필요에 따라 배열 한칸씩을 가위질로 잘라 붙이거나 떼어주는 새로운 패러다임이 필요하게 된 것이지요.

링크드리스트가 어려운 이유 중 하나는 'for문', 'if문' 처럼 '링크드리스트' 한 개만 배우고 땡 그런게 아니라

클래스(혹은 구조체)도 알아야 되고, 동적할당도(일반적으로는) 알아야 하고 포인터도 알아야 하고, 배열에 이용되는 어떤 자료관리의 개념도 알고 있어야 합니다. 

포인터가 활용되면서 부터는 리스트 연결이 눈에 딱 보이는게 아니라 뭔가 추상적인 부분이 있어 처음에는 노트에 도식화 하거나 디버깅을 찍어 보는 것이 조금 번거롭더라도 익숙해지는 지름길이라고 하시더군요(사로자바님이)  

어쨌든 의외로 링크드리스트의 코딩은 의사가 되어서 수술을 하는 것과 같이 신기하기도 하고, 하다보면 꽤 아기자기한 맛이 있답니다. 

다만, 시작하기전 유의하면 매우 편리해지는 개념들이 몇 가지 있는 것 같아 적어 두고자 합니다.

1. int나 float와 같은 자료형이 프로그래머에 의해 미리 정의됩니다. 

자료형에는 data부와 link부로 나뉘어 지는데 link부를 통해서 포인터가 옮겨 다닐수 있어야 하므로 자신의 자료형과 같은 형태의 링크 끈으로 정의 해 줍니다.

(Node* tail; - 자기 자신을 부르고 이런거 아닙니다)

class Node

{

public:

string txt;            //data

Node* tail;          //끈 (여기서는 앞서 만들어진 노드를 찾아가므로 꼬리만 만들었다) 

};

2. 링크드리스트를 만드는 방법은 다양합니다.

알듯말듯 계속 모르는 이유가.. 만드는 방식과 순서가 사람마다 다양하기 때문입니다. 소스를 따라하는 것 보다 한 줄, 한 줄 이해하는 것이 더 맞는 것 같습니다. 헤더부터 달려 있는 링크가  꼬리를 물어간다고 생각할 수 있으나 일반적으로는  머리 앞에 또 머리를 만들고.. 머리기준(Head)이라는 것을 앞으로 당기는 방식을 사용합니다. 즉, 이렇게 만들면 최근에 만들어진 것이 가장 앞에 오게 되겠죠

3. 단어사용을 명확하게 정의하고 시작하는 것이 좋습니다.

링크드리스트 전체의 머리를 head, 뒤를 tail 이라 하고 또.. 이중 링크드리스트에 와서 자료형 속의 앞끈을 head, 뒷끈을 tail, temp, start 책마다 단어는 같고 의미는 다르고 뭐 이러다보면 머리 속이 복잡해지죠..  (1루수 '누구' 이야기 참조)

저는 편의상 자료형(Node)의 끈을 head, tail

링크전체의 시작을 Node *LinkHead

임시로 만든 자료형(Node) 객체 전체의 주소를 Node *tempPoint라 해 두겠습니다.

4. NULL 초기화를 시켜주거나 동적할당을 왜 하는지 명확히 알아야합니다.

일괄적으로 Head도 시켜주고 temp도 시켜주고, 이렇게 짜면 다시 짤 때 막혀버리는 경우가 많습니다.

while(tempPoint->tail!=NULL)  tempPoint=tempPoint->tail; 

이런식으로 링크의 빈자리를 추적해 들어가서 값을 넣어주거나 하는 작업을 하게 되는데 NULL 초기화를 시켜주지 않아서 찾아가다 에러가 나거나 하는 경우가 많습니다.

5. 마지막으로.. 변수를 스왑(바꿔치기)하는 경우를 생각하면 쉽습니다.

이 부분을 다시 한번 설명할텐데 A 와 B를 스왑하는 경우 보통 temp=A, A=B, B=temp로 temp에 값을 저장해 두게 되지요. 마찬가지입니다. 다음차례에 다른 노드가 현재의 노드를 찾아오기 위해서 현재노드의 주소를 임시로 저장해 두는 개념을 가지고 있습니다.

 

그럼 이제, 코드를 한번 볼까요.

class Node    //자료형을 정의합니다.

{

public:

string txt;

Node* tail;

};

class SLL                                          //리스트를 구현할 클래스입니다.

{

public:

Node *LinkHead;

Node *tempPoint;

SLL()

{

LinkHead=NULL;         //한번만 초기화가 되면 됩니다. 두번째부터는 '이전에 만들어졌던 노드의' 주소가 들어가게 되지요

}

void CreatLinkToFirst(string txt)

{

Node*temp = new Node();    //임의로 temp를 하나 만들어 채워넣기 위해 메모리를 할당합니다.

temp->txt = txt;                    //데이터부를 채우고

temp->tail = LinkHead;         //① : 다리를 달아주는데 LinkHead에 저장되어 있는 '이전에 만들어졌던 노드' 주소를 넣어줍니다. 처음엔 NULL임

LinkHead = temp;         //② : LinkHead에 (다음차례를 위해) temp의 주소를 저장해 주는 곳입니다. 

}

void PrintAll()

{

tempPoint=LinkHead;            //출력을 위해 포인터가 옮겨 다닐 예정이므로 LinkHead를 복사해서 사용합니다. 일반적인 방법.

while(tempPoint->tail!=NULL)   

{

cout<<tempPoint->txt<<" -> ";

tempPoint=tempPoint->tail;      // 비어있는 곳까지 계속 찾아들어가죠

}

cout<<tempPoint->txt<<endl;

}

};

int main()

{

SLL *rainbow = new SLL();

rainbow ->CreatLinkToFirst("빨강");

rainbow ->CreatLinkToFirst("주황");

rainbow ->CreatLinkToFirst("노랑");

rainbow ->CreatLinkToFirst("초록");

rainbow ->CreatLinkToFirst("파랑");

rainbow ->CreatLinkToFirst("남색");

rainbow ->CreatLinkToFirst("보라");

rainbow ->PrintAll();

return 0;

}

예전에 저는 ①번과 ②번이 참 헷갈리더라구요.

   ①    temp->tail = LinkHead;  이렇게 넣어준 뒤 

   ②    LinkHead = temp;          이렇게 해 주면 바로

    temp->tail = temp;         이..이런느낌이 되나? 저의 순수함에 혹시 당황하셨나요 ㅋ

아닙니다. 1번은 이전루트에 저장해 두었던 노드의 주소를 현재 테일에 넣어서 이어주는 것이고

2번은 다음루트에 실행될 1번을 위해 미리 저장 해 두는 것입니다. 서로 연결되지 않는 이야기 입니다.

이런 식으로 뒤로 쭉쭉 밀려나가죠. 내용을 그려봤는데.. 그림이 더 어려운 것 같아서.. ㅠ

싱글링크드리스트를 명확하게 알고 있다면 더블, 환형(원형)링크드리스트 이런 것이 크게 어렵지는 않습니다. 다음시간에는 비교적 가장 활용도가 높은 더블링크드리스트를 다양한 기능의 함수와 함께 만들어 보려구해요.