싱글 링크드 리스트

서론

아카데미 중간쯤에 정말 미친듯이 타임어택을 쳤던 그 코드!!

지금 하면 또 될지 모르겠지만 일단 구조 파악하는덴 역시.. 최강..

 

코드

#include <iostream>
#include <cstring>
using namespace std;

// 요소(데이터부)
typedef struct tagElement
{
    int        id;        // id로검색(중복체크)
    char    name[ _MAX_FNAME ];
}ELEMENT,*LPELEMENT;

// 노드
typedef struct NODE
{
    // 정적 상수인 정수 계열 데이터 멤버만 클래스 내부에서 초기화될 수 있습니다.
    static int nodeCount;
    LPELEMENT    element;    // 원소
    NODE        *next;        // 다음노드
}NODE,*LPNODE;

// 외부 초기화
int        NODE::nodeCount = 0;

// 리스트초기화
void    initList( LPNODE &head );
// 앞에 삽입
void    push_front( LPNODE &head, const LPELEMENT element );
// 뒤에 삽입
void    push_back( LPNODE &head, const LPELEMENT element );
// 앞에서 삭제
void    pop_front( LPNODE &head );
// 뒤에서 삭제
void    pop_back( LPNODE &head );

// 모두삭제
void    clear( LPNODE &head );
// 노드 검색
LPNODE    find( const LPNODE head, int findID );
// 노드 검색
LPNODE    find( const LPNODE head, const char *name );

// 편의
// 새로운 노드생성 및 초기화
LPNODE    getNewNode( const LPELEMENT element );
void deleteNode(LPNODE head);

// 출력
void    outputList( const LPNODE head );

void main( void )
{
    // 헤더선언
    LPNODE    head = NULL;

    // 초기화
    initList( head );
    // 원소삽입테스트용
    ELEMENT data;
    
    // 처음삽입
    data.id = 1;
    strcpy_s( data.name , _MAX_FNAME, "1길동");
    push_front( head, &data );
    outputList( head );

    data.id = 2;
    strcpy_s( data.name , _MAX_FNAME, "2길동");
    push_front( head, &data );
    outputList( head );

    data.id = 3;
    strcpy_s( data.name , _MAX_FNAME, "3길동");
    push_front( head, &data );
    outputList( head );

    // 마지막삽입
    data.id = 4;
    strcpy_s( data.name , _MAX_FNAME, "4길동");
    push_back( head, &data );
    outputList( head );

    data.id = 5;
    strcpy_s( data.name , _MAX_FNAME, "5길동");
    push_back( head, &data );
    outputList( head );

    data.id = 6;
    strcpy_s( data.name , _MAX_FNAME, "6;길동");
    push_back( head, &data );
    outputList( head );

    // 처음삭제
    pop_front( head );
    outputList( head );

    pop_front( head );
    outputList( head );

    // 마지막삭제
    pop_back( head );
    outputList( head );

    pop_back( head );
    outputList( head );

    // 찾기테스트
    // ID찾기
    LPNODE    findNode = find( head, 1 );

    if( NULL != findNode )
    {
        cout << findNode->element->id << endl;
        cout << findNode->element->name << endl;
    }
    findNode = find( head, "4길동" );
    // 이름찾기
    if( NULL != findNode )
    {
        cout << findNode->element->id << endl;
        cout << findNode->element->name << endl;
    }

    // 모두삭제
    clear( head );
    outputList( head );
}

// 리스트초기화
void    initList( LPNODE &head )
{
    // 헤더가 널이아니면
    if( NULL != head )
    {
        // 모두삭제
        clear( head );
    }
    // 헤더초기화
    head = NULL;
    NODE::nodeCount = 0;
}
// 앞에 삽입
void    push_front( LPNODE &head, const LPELEMENT element )
{
    // 헤더가 널이냐
    if( NULL == head )
    {
        // 함수버전
        head = getNewNode( element );
    }
    else
    {
        // 헤더갈아치우기
        LPNODE newNode = getNewNode( head->element );
        // 새로운노드삽입
        memmove_s( head->element, sizeof(ELEMENT), element, sizeof( ELEMENT));
        // 새로운노드와 연결
        newNode->next = head->next;
        // 헤더의 다음을 새노드로
        head->next = newNode;
    }
    // 노드 개수 증가
    NODE::nodeCount++;
}
// 뒤에 삽입
void    push_back( LPNODE &head, const LPELEMENT element )
{
        // 헤더가 널이냐
    if( NULL == head )
    {
        // 함수버전
        head = getNewNode( element );
    }
    else
    {
        LPNODE    tempNode = head;
        // 마지막노드찾기
        while( NULL != tempNode->next )
        {
            tempNode = tempNode->next;
        }

        // 다음노드연결
        tempNode->next = getNewNode(element);
    }
    // 노드 개수 증가
    NODE::nodeCount++;
}
// 앞에서 삭제
void    pop_front( LPNODE &head )
{
    if( NULL == head )
    {
        return;
    }

    // 헤더가 널이냐
    if( NULL == head->next )
    {
           // 헤더지우기
        deleteNode(head);
    }
    else
    {
        // 헤더의 다음백업
        LPNODE  headNext = head->next;
        deleteNode(head);
        // 헤더가 다음노드 물기
        head = headNext;
    }
    NODE::nodeCount--;
}

// 뒤에서 삭제
void    pop_back( LPNODE &head )
{
    // 헤더가 널이냐
    if( NULL == head->next )
    {
        deleteNode(head);
    }
    else
    {
        // 헤더의 다음백업
        LPNODE    delPrev = head;
        LPNODE    delNode = head->next;

        while( NULL != delNode->next )
        {
            // 다음으로
            delPrev = delPrev->next;
            delNode = delNode->next;
        }
        // delNode의 다임이 널이라는 소리다!!!
        deleteNode(delNode);
        // 이전꺼
        delPrev->next = NULL;
    }
    NODE::nodeCount--;
}

// 모두삭제
void    clear( LPNODE &head )
{
    while( NULL != head )
    {
        // 모드지우기( 널일때까지 )
        LPNODE back = head->next;

        // 지우기
        deleteNode(head);
        // 다음노드로
        head = back;
    }
    // 노드개수 0
    NODE::nodeCount = 0;
}
// 노드 검색
LPNODE    find( const LPNODE head, int findID )
{
    // 같은 ID의 노드 찾기
    if( NULL != head )
    {
        LPNODE tempNode = head;

        while( NULL != tempNode )
        {
            // 쇼트 서킷트기법에 의해
            if( NULL != tempNode->element && tempNode->element->id == findID )
            {
                return tempNode;
            }
            // 순회
            tempNode = tempNode->next;
        }
    }
    
    return NULL;
}
// 노드 검색
LPNODE    find( const LPNODE head, const char *name )
{
    // 같은 이름의 노드 찾기
    if( NULL != head )
    {
        LPNODE tempNode = head;

        while( NULL != tempNode )
        {
            // 쇼트 서킷트기법에 의해
            if( NULL != tempNode->element && 
                strcmp(tempNode->element->name , name) == 0 )
            {
                return tempNode;
            }
            // 순회
            tempNode = tempNode->next;
        }
    }
    
    return NULL;
}

// 편의
// 새로운 노드생성 및 초기화
LPNODE    getNewNode( const LPELEMENT element )
{
    // 노드 선언 및 할당
    LPNODE    newNode = new NODE;
    // 원소할당
    newNode->element = new ELEMENT;
    // 노드의 원소 복사
    memmove_s( newNode->element , sizeof( ELEMENT ), element,  sizeof( ELEMENT ) ); 
    // 새로운 노드의 다음을 널로
    newNode->next = NULL;
    // 새로운 노드 반환
    return newNode;
}

void deleteNode(LPNODE delNode)
{
        // 헤더지우기
        if( NULL != delNode->element )
        {
            delete delNode->element;
            delNode->element = NULL;
        }
        delete delNode;
        delNode = NULL;
}

// 출력
void    outputList( const LPNODE head )
{
    cout <<"==================== 리스트 출력 ===================="<<endl;
    cout <<"노드개수 : " << NODE::nodeCount << endl;
    // 헤더확인
    if( NULL != head )
    {
        // 임시물기
        LPNODE    tempNode = head;
        // 출력    
        while( NULL != tempNode )
        {
            if( NULL != tempNode->element )
            {
                cout << "ID : " << tempNode->element->id << endl;
                cout << "NAME : " << tempNode->element->name << endl;
            }
            // 다음으로 이동
            tempNode = tempNode->next;
        }
    }
    cout <<"====================================================="<<endl;
}