[자료구조] 싱글 링크드 리스트(Singly Linked List / SLL) - 코딩밥상

싱글 링크드 리스트란?

링크드 리스트는 노드를 연결해서 만든 리스트입니다. 링크드 리스트의 노드는 데이터를 보관하는 필드와 다음 노드와의 연결 고리 역할을 하는 포인터로 이루어집니다. 이를 다음 그림과 같이 노드들을 한 방향으로 연결한 것이 싱글 링크드 리스트입니다.

출처 : 위키 백과

본격적으로 싱글드 리스트의 ADT를 구현하기 전에, 노드를 구조체로 표현해봅시다.

typedef struct tagNode{
    ElementType Data;
    struct tagNode* NextNode;
} Node;

각각의 노드는 데이터값과 다음 노드의 주소를 가리키는 포인터를 갖습니다.

 

---

주요 연산(ADT)

• 노드 생성 연산

Node* SLL_CreateNode(ElementType NewData){  //노드 생성
    Node* NewNode = (Node*)malloc(sizeof(Node));
    
    NewNode->Data = NewData;
    NewNode->NextNode = NULL;
    
    return NewNode;
}

molloc()함수로 노드 구조체의 크기만 한 메모리를 Heap공간에 할당하고 NewNode포인터에 그 메모리 주소를 저장합니다.

노드를 하나 생성하는 과정이기 때문에 NextNode에 올 노드는 아직 모르는 상태이기 때문에 NULL로 비워줍니다.

 

---

• 노드 추가 연산

void SLL_AppendNode(Node** Head, Node* NewNode){    //노드 추가
    if((*Head) == NULL){    //헤드 노드가 NULL이면(노드가 없으면), 새로운 노드가 Head
        *Head = NewNode;
    }
    else{   //테일을 찾아 NewNode를 연결
        Node* Tail = (*Head);
        while(Tail->NextNode != NULL){
            Tail = Tail->NextNode;
        }
        
        Tail->NextNode = NewNode;
    }
}

 앞서 말했듯이, 단일 링크드 리스트에서는 한방향으로 노드가 붙기때문에 테일의 노드 뒤에만 새로운 노드를 만들면 됩니다.

따라서 만약 리스트가 비어있다면 새로 추가되는 노드가 Head노드가 되고, 만약 비어있지 않다면 Tail노드의 NextNode값이 추가될 NewNode의 주소를 가리키면 됩니다.

 

⚠️여기서 궁금증! 왜 매개변수가 더블 포인터가 될까요?

위 SLL_AppendNode()함수는 List의 헤드가 NULL일 때 새 노드를 헤드로 만듭니다. 하지만 Node* Head를 매개변수로 넘겨주면 함수 실행 전 List의 주소와 앞 서 생성한 노드의 주소를 '복사'해서 매개변수로 넣습니다.

즉 List포인터가 담고 있는 주소값만 복사되고, 정작 List 포인터 변수의 주소는 전달되지 않는 것입니다. 

따라서 포인터 값이 아닌, 포인터 자신의 주소를 넘겨야하기 때문에 매개변수를 더블포인터로 넘겨야 합니다. 

 

 

---

• 노드 소멸 연산

void SLL_DestroyNode(Node* Node){   //노드 소멸
    free(Node);
}

노드가 존재하는 주소를 가리키는 포인터를 입력받아 free()함수에 넘겨 해당 공간을 소멸시킵니다.

 

 

---

• 노드 탐색 연산

Node* SLL_GetNodeAt(Node* Head, int Location){    //노드 탐색
    Node* Current = Head;
    
    while(Current != NULL && (--Location) >= 0){    //Head노드부터 하나씩 넘어가며 탐색
        Current = Current->NextNode;
    }
    
    return Current;
}

헤드부터 시작해서 다음노드로 차근차근 노드의 개수만큼 거쳐야 원하는 요소에 접근할 수 있습니다. 찾고자 하는 요소가 N번째에 있다면 N-1개의 노드를 거쳐야 하는 것입니다.

 

 

---

• 노드 삭제 연산

void SLL_RemoveNode(Node** Head, Node* Remove){     //노드 삭제
    if (*Head == Remove){   //Head를 삭제할 경우
        *Head = Remove->NextNode;
    }
    else{
        Node* Current = *Head;      //Head부터 삭제할 노드를 탐색
        while(Current != NULL && Current->NextNode != Remove){
            Current = Current->NextNode;
        }
        
        if(Current != NULL){    //삭제 노드 전의 노드와 삭제 노드 다음 노드를 연결
            Current->NextNode = Remove->NextNode;
        }
    }
}

삭제할 노드를 탐색 한 후 해당 노드의 연결을 끊어줍니다.

끊어진 부분을 건너 뛰어 NextNode값을 다음 노드로 연결해줍니다.

만약 삭제한 노드를 다시 사용 안한다면 앞서 보았던 소멸 연한 SLL_DestroyNode(Remove)와 같이 소멸시켜야 메모리 누수를 막을 수 있겠죠?

 

 

---

• 노드 삽입 연산

void SLL_InsertAfter(Node* Current, Node* NewNode){     //노드 삽입
    NewNode->NextNode = Current->NextNode;  //현재 노드와 삽입할 노드, 그 다음 노드의 연결을 새로함
    Current->NextNode = NewNode;
}
void SLL_InsertNewHead(Node** Head, Node* NewHead){		//리스트가 비어있을 경우(삽입하는 노드가 헤드가 되는 경우)
    if(Head == NULL){
        (*Head) = NewHead;
    }
    else{
        NewHead->NextNode = (*Head);
        (*Head) = NewHead;
    }
}

노드를 중간에 삽입하게 되면 리스트에 형성된 연결들을 재설정 해줍니다. 삽입되는 노드의 전 노드의 NextNode가 삽입되는 노드를 가리키고 삽입되는 노드의 NextNode는 기존의 전 노드의 NextNode값을 받으면 되겠네요. 글로 설명하려니 말장난 하는거 같네요..

저는 머리속에 그림을 그리며 기차놀이를 한다고 생각하니 이해가 쉬웠습니다.

 

만약 삽입되는 노드가 헤드노드가 될 경우도 따로 생각해 줍니다. 이 경우는 중간에 끼는게 아니기 때문에 삽입되는 노드의 NextNode가 가리키는 값만 신경써주면 되겠네요.

 

 

---

• 노드 개수 세기 연산(번외)

int SLL_GetNodeCunt(Node* Head){    //노드 갯수 세기
    int count = 0;
    Node* Current = Head;
    
    while(Current != NULL){ //Head부터 Tail까지 카운트 업
        Current = Current->NextNode;
        count++;
    }
    return count;
}

이는 위에서 봤던 탐색 과정에서 카운트하는 연산만 추가해주면 되겠죠?

 

 

---

링크드 리스트의 장단점

 

직접 구현하고 보니 장단점을 확실히 알 수 있었습니다.

정리해봅시다.

단점

• 다음 노드를 가리키는 포인터가 필요하기 때문에 각 노드마다 추가적인 메모리가 필요
• 특정 위치에 있는 노드에 접근하기 위한 비용이 크며 접근하기까지 시간이 많이 소요(탐색이 오래걸림)

장점

• 새로운 노드의 추가,삽입,삭제가 쉽고 빠름
• 현재 노드의 다음 노드를 얻어오는 연산에 대해서 비용이 없음

요약해보자면, "노드의 추가,삽입,삭제 연산은 빠르지만 특정 위치에 있는 노드에 접근하는 연산은 느리다." 입니다.