[자료구조] 연결 리스트 (Linked Lists)

단순 연결 리스트(Singly Linked Lists and Chains)

순차리스트의 특성

- 데이터 객체의 연속된 원소들이 일정 거리만큼 떨어져 저장

-(배열) a_i,j가 L_ij에 저장된다면, a_i,j+1은 L_ij+1에 저장

-(스택) 제일 위의 원소가 

-(큐) 큐의 i번째 요소가 L_i에 위치하면 i+1 ->(L_i+1)%n

 

임의의 원소에 대한 삽입(Insertion)과 삭제(Deletion)에 많은 비용

- 중간에 하나의 삽입/삭제에 대해 다른 원소들의 이동이 필요하기 때문.

 

연결(linked) 표현

- 순차 표현에서 제기된 데이터 이동 문제점 해결

- 각 원소들이 메모리 내의 어떤 곳에나 위치 가능

- 원소에 정확한 순서로 접근하기 위한 정보가 필요(주소 정보)

 

노드(node)

- 0개 이상의 데이터 필드

- 1개 이상의 link 또는 pointer: 다음 원소를 가리킴

 

연결리스트의 일반적인 방법

- 노드들을 순차적으로 표시하고 링크를 화살표로 표현

- 화살표로 다음 노드를 직관적으로 가리킴

## !NOTE! ##

-노드들은 실제로 메모리 순차적 위치에 존재하지 않는다.

-노드들의 위치(주소)는 실행시마다 바뀔 수 있다. (malloc의 영향)

-link가 0(NULL)인지 검사하는 것 외에는 특정 주소 값을 찾지 않는다.

 

Insertion 과정

- 사용하지 않는 노드 하나를 가져온다

- 넣을 데이터를 노드의 데이터 필드에 넣고

- 넣을 위치의 앞 노드에 새 노드의 주소값을, 새 노드의 주소값에는 뒷 노드의 주소값을 넣는다.

(주소를 넣을 때에 앞 노드의 link 필드 값을 가져오는 방법도 있다.)

 

Deletion 과정

- 삭제할 노드의 앞 노드를 찾고

- link를 삭제할 노드의 다음 노드 주소로 수정한다.

 

 

C에서의 체인 표현(Representing chains in C)

노드 구조 (struct)

자기와 동일 타입에 대한 링크 (self-referential structure)

노드 생성시 메모리 할당 (malloc())

노드 메모리 해제 (free())

 

// 새로운 공백 리스트 생성
listPointer first = NULL;

// 공백 리스트인지 검사 매크로
#define IS_EMPTY(first)(!(first))

// 새로운 노드를 생성하기 위한 매크로 MALLOC
MALLOC(first, sizeof(*first)); //sizeof(*first) == 16byte

 

노드의 필드값 정의: -> 연산자 사용

예시) first->link = NULL;

또는) *(first).link = NULL;

 

+삽입과 삭제는 위와 동일하게.

삭제시에는 trail이라는 삭제할 노드의 선행노드를 가리키는 포인터를 사용.

 

 

연결 스택과 큐(Linked Stacks and Queues)

여러 개의 스택/큐가 동시에 있을 떄- 다중 스택과 큐를 순차적으로 표현할 때, 많은 오버헤드 발생

 

연결 스택과 큐

- 링크의 화살표 방향: 노드의 삽입과 삭제가 편리하게 만들어 줌

- (연결 스택) 톱에서 노드 삽입/삭제 용이

- (연결 큐) 뒤에선 노드를 쉽게 삽입, 앞에선 노드를 쉽게 삭제

 

연결 스택

#define MAX_STACKS 10 //스택 최대 수
typedef struct{
	int key;
    /* 기타 필드 */
    } element;
    
typedef struct stack *stackPointer;

typedef struct stack {
	element data;
    stackPointer link;
};
stackPointer top[MAX_STACKS];

//PUSH
void push(int i, element item)
{
	stackPointer temp;
    MALLOC(temp, sizeof(*temp));
    temp->data = item;
    temp->link = top[i];
    top[i] = temp;
}

//POP
void pop(int i)
{
	stackPointer temp = top[i];
    element item;
    if(!temp) return stackEmpty();
    item = temp->data;
    top[i] = temp->link;
    free(temp);
    return item;
}

 

연결 큐

#define MAX_QUEUE 10 //큐의 최대 수
typedef struct queue *queuePointer;

typedef struct queue {
	element data;
    queuePointer link;
};

queuePointer front[MAX_QUEUES];
queuePointer rear[MAX_QUEUES];

// 큐 뒤에 삽입
void addq(i, item)
{
	queuePointer temp;
    MALLOC(temp, sizeof(*temp));
    temp->data = item;
    temp->link = NULL;
    
    if(front[i]) rear[i]->link = temp;
    else front[i] = temp;
    
    rear[i] = temp;
}

// 앞에서부터 삭제
element eleteq(int i)
{
	queuePointer temp = front[i];
    element item;
    
    if(!temp) return queueEmpty();
    item = temp -> data;
    front[i] = temp->link;
    
    free(temp);
    return item;
}

 

연결리스트로 n-stack/m-queue를 구현-> 구현의 단순함+Time Complexity의 감소.

: 추가공간을 위한 이동이 사라짐

가용 메모리가 남아있을 때까지 크기 증대 가능 (malloc())

링크에 대한 오버헤드가 발생하나, 장점이 많음.

: time 감소, space 증가

 

 

다항식(Polynomials)

리스트를 사용한 다항식 표현

- node: 계수, 지수, 포인터

- 계수는 정수라고 가정

typedef struct polyNOde *polyPointer;
typedef struct polyNode {
	int coef;
    int expon;
    polyPointer link;
};
polyPointer a,b;

 

다항식 덧셈

a->expon과 b->expon을 비교

case1) 같은 경우

- 계수를 더하고

- 결과 다항식에 새로운 항을 만든후

- 둘다 다음 노드로 이동

case2) 한쪽이 큰 경우

- 큰 쪽과 같은 항을 만들어 결과 다항식에 첨가

- 큰 쪽을 다음 노드로 이동

 

세 가지 비용 요소

- 계수 덧셈

- 지수 비교

- 결과값을 위한 새로운 노드

 

다항식의 곱셈

a(x)*b(x)+d(x)이면

곱을 먼저 진행하여 임시 항(temp)를 만들고,

temp와 d(x)를 연산한 후, temp를 반환하여 메모리 가용도 높이기 가능.

 

다항식의 원형 리스트 표현

- 마지막 노드가 리스트의 첫 노드를 가리키도록 함.

- 해제된 노드를 체인 형태의 리스트로 유지

- 가용 공간 리스트 혹은 avail 리스트

• avail: 리스트에서 첫 번째 노드를 가리키는 포인터(초기값 NULL)

- 새로운 노드가 필요하면 이 리스트를 조사

- malloc, free 대신 getNode, retNode 사용

polyPointer getNOde(void)
{
	polyPointer node;
    if(avail){
    	node = avail;
        avail = avail->link
    }
    else MALLOC(node, sizeof(*node));
    
    return node;
}

void retNode(polyPointer node)
{
	node->link = avail;
    avail = node;
}

void cerase(polyPointer *ptr)
{
	polyPointer temp;
    if(*ptr) {
    	temp = (*ptr)->link;
        (*ptr)->link = avail;
        avail = temp;
        *ptr = NULL;
    }
}

 

제로 다항식

- 기존 방식으로는 제로 다항식에 별도 케이스를 만들어 처리

- 헤더 노드 사용하여 다항식 처리.(각 다항식은 헤더 노드를 갖도록 함)

 

 

추가 리스트 연산(Additional List Operation)

체인을 역순으로 만드는 (inverting, reversing) 연산

listPointer invert(listPointer lead)
{
	listPointer middle, trail;
    middle = NULL;
    while (lead) {
    	// 리스트 첫 노드를 가리키는 lead를 옮겨가며 middle과 trail로 연결 수정
    	trail = middle;
        middle = lead;
        lead = lead->link;		//미리 링크를 옮겨둠.(링크가 있을 때 이동)
        middle->link = trail; //이부분이 핵심. 이전 노드(trail)을 현 노드(middle)의 link에 연결.
    }
}

 

두 개의 체인 ptr1과 ptr2를 연결(concatenation)하는 연산

listPointer concatenate(listPointer ptr1, listPointer ptr2)
{
	listPointer temp
    
    // 둘 중 하나가 NULL이면 다른 리스트 리턴
    if(!ptr1) return ptr2;
    if(!ptr2) return ptr1;
    
    // temp를 ptr1의 마지막 노드로 이동
    for(temp = ptr1; temp->link; temp=temp->link) ;
    
    temp->link = ptr2;

}

 

원형 연결 리스트에 삽입

리스트의 마지막 노드 포인터 last를 유지

void insertFront(listPointer *last, listPointer node)
{
	// 리스트가 공백이면 last가 새로운 항목을 포인팅
	if(IS_EMPTY(*first)){
    	*last = node;
        node->link = node;
    }
    else {
    	node->link = (*last)->link;
        (*last)->link = node;
    }
}

// 길이 계산
int length(listPointer last)
{
	listPointer temp;
    int count = 0;
    
    if (last) {
    	temp = last;
        
        do{
        	count++;
            temp = temp->link;
        }while(temp != last);
    }
}

 

 

희소행렬(Sparse Matrices)

- 희소행렬의 각 열과 행을 헤더 노드가 있는 원형 연결 리스트로 표현

- 각 노드에는 헤더노드와 엔트리 노드를 나타내기 위한 tag 필드 존재

 

헤더 노드(header)

- down: 열 리스트로 연결하는데 사용

- right: 행 리스트로 연결하는데 사용

- next: 헤드 노드들을 서로 연결하는데 사용

- 헤더 노드의 총 수: max{행의 수, 열의 수}

 

엔트리 노드(entry)

- tag 필드 외에 5개 필드(row, col, down, right, value)

- down: 같은 열에 있는 0이 아닌 다음 항 연결

- right: 같은 행에 있는 0이 아닌 다음 항 연결

 

필요한 노드 수

max{numRows, numCols} + numTems + 1

: 맨 앞항은 header 수, 뒤는 entry 수, 마지막 1은 header node list

#define MAX_SIZE 50 /* 최대 행렬 크기 */
typedef enum {head,entry} tagfield;
typedef struct matrixNode *matrixPointer;
typedef struct entryNode {
    int row;
    int col;
    int value;
};

typedef struct matrixNode {
    matrixPointer down;
    matrixPointer right;
    tagfield tag;
    union {
        matrixPointer next;
        entryNode entry;
    } u;
};
matrixPointer hdnode[MAX_SIZE];

 

입력을 할 때는 보조 배열 hdnode를 사용

- 적어도 입력될 행렬의 가장 큰 차원의 크기라고 가정

- 변수 hdnode[i]: 열 i와 행 i에 대한 헤더 노드를 가리키는 포인터

: 입력행렬을 구성하는 동안 임의의 열을 효과적으로 접근할 수 있게 함.

 

출력의 시간 복잡도: O(numRows+numTerms)

삭제의 시간 복잡도: O(numRows+numCols+numTerms)

 

 

이중 연결 리스트(Doubly Linked List)

- 포인터를 양방향으로 이동할 필요가 있을 떄

- 임의의 노드를 삭제해야 되는 문제에 적합

- 각 노드는 전방과 후방을 가리키는 두 개의 링크를 가짐

 

임의의 노드 ptr에 대해

ptr == ptr->llink->rlink == ptr->rlink->llink 성립

 

// insertion
void dinsert(nodePointer node, nodePointer newnode)
{
	//node의 오른쪽에 newnode 삽입
    newnode->llink = node;
    newnode->rlink = node->rlink;
    node->rrlink->llink = newnode;
    node->rrlink = newnode;
}

//delete
void ddelete(nodePointer node, nodePointer deleted)
{
	if(node == deleted) printf("NOT PERMITTED: Head Node Deletion");
    else{
    	deleted->llink->rlink = deleted->rlink;
        deleted->rlink->link = deleted->llink;
        free(deleted);
    }
}