C++ 싱글 링크드 리스트 구현

<출처> http://blog.naver.com/PostList.nhn?from=postList&blogId=tius1234&categoryNo=6&parentCategoryNo=6&currentPage=8

 

싱글 링크드 리스트 구현

 

 

링크드 리스트는 말 그대로 리스트이되, 서로 링크가 되어있는 리스트이다. 직역하자면 연결된 리스트가 된다. 우선 위의 이미지를 보고 설명을 하자면, Datum 이라는 공간에 데이터가 들어가는 것이고 Link라고 적혀있는 공간에는 다음 노드에 대한 포인터. 즉, 주소값이 들어가게 된다.

 

우선 노드라는 단어를 먼저 정의하고 넘어가야 하는데, 만약 서로 연결되는 것을 선으로 표현하고, 실제 존재하는 것(위의 이미지에서는 Datum과 Link)은 하나의 점이라고 생각을 합시다. 지금 이렇게 설명을 하는 이유는 전기적인 회로, 혹은 통신에서 하나의 노드, 그리고 링크라는 개념이 그러한 개념이기 때문이다. 무슨 이야기냐면, 영어에서 한글로 번역을 하다보면 정확하게 한가지 의미로 번역할 수 있는 것이 아니라, 대략적으로 이러한 느낌의 것을 영어로 이렇게 이야기를 하는구나, 라고 생각하고 넘어가는 것이 오히려 편리한 경우가 종종 있어서 적고 넘어가는 것이다.

 

위의 이미지와 책의 이미지는 다소 다르지만, 시작하는 노드를 헤드라고 이야기하고, 가장 마지막 노드를 테일이라고 이야기를 한다.

 

 

• 링크드 리스트의 장점
• 새로운 노드의 추가, 삽입, 삭제가 쉽고 빠르다.
• 링크드 리스트의 단점
• 다음 링크를 가리키는 포인터가 4 Byte씩 잡아먹는다.
• 첫 노드부터 마지막 노드까지 순서대로 검색을 하기 때문에, 최악의 경우 배열보다 자료를 검색하는데 들어가는 시간이 더 걸릴 수 있다.

 

 

[참고 소스 코드]

 

 

#include <stdio.h>
#include <time.h>
#include <stdlib.h>
  
class SList{
public:
    struct ListData
    {
        int nData;
        ListData *pNext;
    };
  
    SList();
    ~SList();
  
    void Insert(int nData); //  데이터 삽입
    bool Delete(int nData); //  데이터 삭제
      
    void DeleteAll();           //  모든 데이터 삭제
  
    int GetData(int nIndex);
  
    unsigned int GetSize();
  
private:
    ListData *m_pHead;  //  리스트 관리를 위한 포인터
};
  
SList::SList()
    : m_pHead(NULL)
{
}
  
SList::~SList()
{
    DeleteAll();
    m_pHead = NULL;
}
  
void SList::Insert(int nData)
{
    if( m_pHead == NULL )
    {
        m_pHead = new ListData();
        m_pHead->pNext = NULL;
        m_pHead->nData = nData;
    }
    else
    {
        ListData *temp = m_pHead;
        m_pHead = new ListData();
        m_pHead->nData = nData;
        m_pHead->pNext = temp;
    }
}
  
bool SList::Delete(int nData)
{
    ListData *temp = m_pHead;
    ListData *temp2 = NULL;
    bool bRet = false;
    while(temp)
    {
        if( temp->nData == nData )
        {
            bRet = true;
            break;
        }
        temp2 = temp;
        temp = temp->pNext;
    }
    if( bRet == false )
        return bRet;
  
    if( m_pHead == temp )
        m_pHead = m_pHead->pNext;
    else
        temp2->pNext = temp->pNext;
    delete temp;
    return bRet;
}
  
void SList::DeleteAll()
{
    ListData *temp = m_pHead;
    ListData *temp2;
    while(temp)
    {
        temp2 = temp->pNext;
        delete temp;
        temp = temp2;
    }
    m_pHead = NULL;
}
  
int SList::GetData(int nIndex)
{
    ListData *temp = m_pHead;
    for(int i=0; temp; ++i, temp = temp->pNext)
    {
        if( i == nIndex )
        {
            return temp->nData;
        }
    }
    return -1;
}
  
unsigned int SList::GetSize()
{
    ListData *temp = m_pHead;
    unsigned int i=0;
    while(temp)
    {
        temp = temp->pNext;
        ++i;
    }
    return i;
}
  
void Draw(SList *pList)
{
    int size = pList->GetSize();
    for(int i=0; i<size; ++i)
    {
        printf("[%d]->", pList->GetData(i));
    }
    printf("[NULL]\n");
}
  
int main(int argc, char **argv)
{
    srand(time(0));
    SList list;
    for(int i=0; i<10; ++i)
    {
        int random = rand()%100;
        list.Insert(random);
        Draw(&list);
    }
  
    list.DeleteAll();
  
    return 0;
}