기본 자료구조; 연결 리스트

연결 리스트

: 여러 노드들의 연결로 이루어진 리스트. 각 노드는 데이터 값을 저장하는 데이터 필드와 다른 노드의 주소값을 저장하는 링크 필드로 이루어져 있다. 노드의 삽입과 삭제가 용이하며 연속된 메모리 공간이 필요하지 않고 배열에 비해 크기 제한이 없다는 장점과 다소 구현이 어렵다는 단점이 있다.

 

 

▷  연결 리스트의 종류

 

- 단순 연결리스트 : 하나의 링크 필드를 이용해 연결. 마지막 노드의 링크 값은 NULL.

 

 

· 단순 연결 리스트 생성

: ListNode 구조체 생성, 동적 메모리를 할당 받아 연결 리스트 생성

//단순 연결 리스트 구현
typedef int element;
typedef struct ListNode{
	element data;
	struct ListNode *link;
} ListNode;

//노드 생성, 동적 메모리 이용
int main(void){
	//연결리스트의 대표 노드(대개 맨 처음 노드)를 가리키는 포인터 변수는 헤드 포인터.
	ListNode *p1;
	p1 = (ListNode*)malloc(sizeof(ListNode));
	p1->data = 10;
	p1->link = NULL;
    
	ListNode *p2 = (ListNode*)malloc(sizeof(ListNode));
	p2->data = 20;
	p2->link = NULL;
	p1->link = p2;
}

 

·단순 연결 리스트 원소 관리 함수

: insert_node(), remove_node() 함수 구현

//단순 연결 리스트의 삽입 연산

//phead; 헤드 포인터 head에 대한 포인터
//p; 삽입될 위치의 선행 노드를 가리키는 포인터, 이 노드 다음에 새로운 노드를 삽입
//new_node; 삽입할 새로운 노드를 가리키는 포인터

void insert_node(ListNode **phead, ListNode *p, ListNode *new_node)
{
	if(*phead == NULL){		//공백 리스트인 경우
		new_node->link = NULL;
		*phead = new_node;
	}
	else if(p == NULL){		//p가 NULL이면 첫 번째 노드로 삽입
		new_node->link = *phead;
		*phead = new_node;
	}
	else{		//p 다음에 삽입
		new_node->link = p->link;
		p->link = new_node;
	}
}


//삭제 연산

//phead; 헤드 포인터에 대한 포인터
//p; 삭제될 노드의 선행 노드
//removed; 삭제될 노드

void remove_node(ListNode **phead, ListNode *p, ListNode *removed)
{
	if(p==NULL)		//첫 번째 노드 삭제
		*phead = (*phead)->link;
	else
		p->link = removed->link;
	free(removed);	//메모리 반납
}

 

· 단순 연결 리스트 원소 출력 관리 함수

: visit(), search() 함수 구현

//방문 연산, 리스트 상의 노드를 순차적으로 방문해 데이터를 출력

//반복기법
//시간복잡도: O(n), 공간복잡도: O(1)
void visit(ListNode *head)
{
    ListNode *p=head;
    while( p!=NULL ){
        printf("%d->",p->data);
        p = p->link;
    }
    printf("\n");
}

//재귀 기법
//시간복잡도: O(n), 공간복잡도: O(n)
void visit_recur(ListNode *head)
{
    ListNode *p=head;
    if( p!=NULL ){
        printf("%d->",p->data);
        visit_recur(p->link);
    }
}


//탐색 연산, 순차탐색

ListNode *search(ListNode *head, element x)
{
    ListNode *p;
    p = head;
    while( p!=NULL ){
        if( p->data == x ) return p;	//탐색 성공
        p = p->link;
    }
    return p;	//탐색 실패일 경우 NULL 반환
}

 

· 단순 연결 리스트 구조 변환(병합, 역순) 함수

: concat(), reverse() 함수 구현

//병합 연산

ListNode *concat(ListNode *head1, ListNode *head2)
{
    ListNode *p;
    if ( head1 == NULL) return head2;
    else if ( head2 == NULL ) return head1;
    else{
        p=head1;
        while( p->link != NULL )
            p = p->link;
        p->link = head2;
        return head1;
    }
}


//역순 연산
ListNode *reverse(ListNode *head)
{
    ListNode *p, *q, *r;
    p = head;	//p는 역순으로 만들 리스트
    q = NULL;	//q는 역순으로 만들 노드
    while( p!=NULL){	//p가 NULL이라면 역순으로 변환해도 NULL. 바로 리턴.
        r = q;	//r은 역순으로 된 리스트. r은 q, q는 p를 차례로 따라간다.
        q = p;
        p = p->link;
        q->link = r;	//q의 링크 방향을 바꾼다.
    }
    return q;	//q는 역순으로 된 리스트의 헤드 포인터
}

 

 

 

- 환형 연결리스트 : 마지막 노드의 링크가 첫 번째 노드를 가르키는 리스트. 헤드 포인터가 마지막 노드를 가리키게끔 구성하면 리스트의 처음이나 마지막에 노드를 삽입하는 연산이 단순 연결 리스트에 비해 용이.

 

 

· 환형 연결 리스트 원소 삽입 함수

: insert_first(), insert_last() 함수 구현

//환형 연결 리스트 삽입 연산

//phead; 리스트의 헤드 포인터의 포인터
//p; 선행 노드
//node; 삽입될 노드

//리스트의 처음에 삽입
void insert_first(ListNode **phead, ListNode *node)
{
    if( *phead == NULL ){	//빈 리스트인 경우
        *phead = node;
        node->link = node;	//환형 연결 리스트이므로 원소가 하나일 때는 link값이 자기 자신을 가리킴.
    }
    else{
        node->link = (*phead)->link;
        (*phead)->link = node;
    }
}


//리스트의 끝에 삽입
void insert_last(ListNode **phead, ListNode *node)
{
    if( *phead == NULL ){
        *phead = node;
        node->link = node;
    }
    else{
        node->link = (*phead)->link;
        (*phead)->link = node;
        *phead = node;
    }
}

 

 

 

 

- 이중 연결 리스트 :  하나의 노드가 선행 노드와 후속 노드에 대한 두 개의 링크를 가지는 리스트. 선행 노드를 찾기 어려운 단순 연결 리스트의 단점을 극복할 수 있다. 공간을 많이 차지하고 코드가 상대적으로 복잡한 것이 단점이다.  일반적으로 이중 연결 리스트는 헤드 노드를 가진 환형 이중 연결 리스트 형태로 사용된다.

 

-- 헤드 노드 : 데이터는 저장되지 않고 단지 삽입, 삭제 연산을 간단하게 할 목적으로 만들어진 특별한 노드. 공백 상태에서는 헤드 노드만 존재하여 헤드포인터가 NULL인 경우를 처리하지 않아도 된다.

 

 

· 이중 연결 리스트 생성

: DlistNode 구조체를 구현. 양방향 리스트라는 의미에서 d를 붙여 구분한다.

typedef int element;
typedef struct DlistNode{
    element data;
    struct DlistNode *llink;
    struct DlistNode *rlink;
}DlistNode;

 

· 이중 연결 리스트 원소 관리 함수

: dinsert_node(), dremove_node() 함수 구현.

//삽입 연산
//new_node를 before의 오른쪽에 삽입한다.

void dinsert_node(DlistNode *before, DlistNode *new_node)
{
    new_node->llink = before;
    new_node->rlink = before->rlink;
    before->rlink->llink = new_node;
    before->rlink = new_node;
}


//삭제 연산
void dremove_node(DlistNode *phead_node, DlistNode *removed)
{
    if( removed == phead_node ) return;
    removed->llink->rlink = removed->rlink;
    removed->rlink->llink = removed->llink;
    free(removed);
}

 

 

 

 

▷ 연결 리스트의 응용: 다항식

 

하나의 다항식을 하나의 연결 리스트로 표현. 각 노드가 하나의 항의 정보(계수, 지수)를 저장한다. 헤드 노드에는 전체 리스트의 길이, 첫 번째 노드와 마지막 노드의 주소를 저장해 연산을 간소화한다.

typedef struct ListNode{	//일반 노드 구조
    int coef;
    int exp;
    struct ListNode *link;
}ListNode;

typedef struct ListHeader{	//헤더 노드 구조
    int length;
    ListNode *head;
    ListNode *tail;
}ListHeader;

 

//다항식의 덧셈 예제

#include <stdio.h>
#include <stdlib.h>

typedef struct ListNode{
    int coef;
    int exp;
    struct ListNode *link;
}ListNode;

typedef struct ListHeader{
    int length;
    ListNode *head;
    ListNode *tail;
}ListHeader;

//초기화 함수
void init(ListHeadr *plist)
{
    plist->length = 0;
    plist->head = plist->tail = NULL;
}

//plist는 연결 리스트의 헤더를 가리키는 포인터, coef는 계수, exp는 지수
void insert_node_last(ListHeader *plist, int coef, int exp)
{
    ListNode *temp = (ListNode*)malloc(sizeof(ListNode));
    if( temp==NULL ) error("메모리 할당 에러");
    temp->coef = coef;
    temp->exp = exp;
    temp->link = NULL;
    if( plist->tail==NULL ){
        plist->head = plist->tail = temp;
    }
    else{
        plist->tail->link = temp;
        plist->tail = temp;
    }
    plist->length++;
}

//list3 = list1 + list2
void poly_add(ListHeader *plist1, ListHeader *plist2, ListHeader *plist3)
{
    ListNode *a = plist1->head;
    ListNode *b = plist2->head;
    int sum;
    while( a && b ){
        if( a->exp == b->exp ){
            sum = a->coef + b->coef;
            if( sum != 0 ) insert_node_last(plist3, sum, a->exp);
            a = a->link; b = b->link;
        }
        else if( a->exp > b->exp ){
            insert_node_last(plist3, a->coef, a->exp);
            a = a->link;
        }
        else{
            insert_node_last(plist3, b->coef, b->exp)'
            b = b->link;
        }
    }
    
    //a나 b 중 하나가 먼저 끝난 경우, 남은 항들을 모두 복사
    for(; a!=NULL; a=a->link)
        insert_node_last(plist3,a->coef,a->exp);
    for(; b!=NULL; b=b->link)
        insert_node_last(plist3,b->coef,b->exp);
}

void poly_print(ListHeader *plist)
{
    ListNode *p = plist->head;
    for(; p; p=p->link)
        print("%d %d\n", p->coef, p->exp);
}