1. 단순 연결리스트(Singly Linked List)

(1) 정의

• 가장 기본적인 형태의 연결 리스트로서, 연결리스트, 선형연결리스트, 체인(Chain)이라고 한다.
• 각각의 노드가 하나의 포인터를 갖는 구조로, 포인터는 다음 노드를 가르킨다.
• 단순 연결리스트에서는 거꾸로 갈 수 있는 방법은 없다. 탐색시간은 포인터를 이용하여 순차적으로 따라가야 하므로, 시간복잡도는 O(n)이다.
  
• 리스트 상의 특정 노드를 액세스하기 위해서는 처음 노드부터 검색한다.
• 한 노드에는 1차원 배열 관계가 있는 다음 노드의 주소를 갖는 한 개의 링크 부분을 두고 있으며 마지막 노드의 링크는 null로 표현하고 해싱 기법에서 오버플로 처리시 체이닝 기법에 이용된다.
• 노드를 삽입, 삭제하는 경우 선행 노드(previous node)를 알고 있어야만 연결조작을 할 수 있다.

해싱 기법에서 오버플로 처리시 체이닝 기법에 이용된다

해싱(hashing)은 데이터를 효율적으로 관리하기 위한 방법 중 하나이다. 해싱에서는 키를 해시 함수에 입력하여 나온 해시값을 인덱스로 사용하여 데이터를 저장하고 검색한다. 그러나 다른 키들이 동일한 해시값을 가질 때 '충돌'이 발생하는데, 이런 경우를 처리하기 위한 한 가지 방법이 '체이닝'이다. 체이닝에서는 같은 해시값을 가진 데이터들을 연결 리스트에 저장하여 관리합니다. 이 때, 단순 연결 리스트가 주로 사용됩니다. 각 해시값에 대응되는 연결 리스트의 헤드가 해시 테이블의 각 슬롯에 저장되며, 충돌이 발생하면 새 노드가 해당 연결 리스트에 추가된다.

노드의 정의

노드는 자기 참조 구조체를 이용하여 정의된다. 자기 참조 구조체란 자기 자신을 참조하는 포인터를 포함하는 구조체이다. 구조체 안에는 데이터를 저장하는 data필드와 포인터가 저장되어 있는 link필드가 존재한다.

(2) 삽입

procedure INSERT(Head, Item, Y)
/* Y:삽입할 노드, X:삽입 후 Y의 선행 노드*/
call GETNODE(Y)
/*삽입할 Y노드를 생성*/
DATA(Y)←item
/*Y노드에 데이터 값을 저장*/
	if (Head=nil) then Head←Y
    /* Head노드가 nil인 경우 Head가 Y를 가리키도록 한다. */
    LINK(Y)←nil
    /* 마지막노드는 항상 null임 */
    else LINK(Y)←LINK(X) /* ② */
    LINK(X)←Y /* ② */
end INSERT

void insert(listPointer *first, listpointer X)
{	/* data = 50인 새로운 노드를 체인 first의 노드 x뒤에 삽입 */
	listPointer temp;
    MALLOC(temp, sizeof(*temp));
    	temp→data = 50l
        if (*first) {
        	temp→link = x→link;
            x→link = temp;
        }
        else {
        	temp→link = NULL;
        	*first = temp;
        }
}

(3) 삭제

procedure DELETE(X, Y, Head)
/* Y: 삭제할 노드, X:Y노드의 선행 노드 */
/
	if (Head = nil) call List-empty
/* 리스트에 노드가 존재하지 않으므로 삭제 노드가 없다. */
if (X=nil) then Head←LINK(Head)
/* 첫 번째 노드 삭제 */
else LINK(X)←LINK(Y)
/* 중간 노드 삭제 */
call RET(Y)
end DELETE

void delete (listPointer *fisr, listPointer trail, listPointer node) {
/* 리스트로부터 노드를 삭제, trail은 삭제될 x의 선행 노드이며 first는 리스트의 시작 */
	if (trail)
    	trail→link = x→link;
    else
        *first = (*first)→link;
        free(x);
}

2.원형 연결리스트(Circular Linked List, 단순연결원형리스트)

(1) 정의

• 단순연결리스트의 마지막 노드가 null link를 갖는 대신에 리스트에서 처음 노드의 포인터를 갖도록 구성한 리스트이다.
• 빠른 리스트의 반환을 위해 원형리스트를 사용한다.
  
• head 포인터가 첫 번째 노드를 가리킬 때 새로운 노드X를 원형 리스트의 첫 번째 노드 앞에 삽입하려고 하면, 마지막 노드의 링크 필드를 변경하기 위해서 마지막 노드를 찾을 때 까지 모든 노드를 탐색해야 하는 문제가 발생한다.
• head 포인터가 마지막 노드를 가리킬 경우, 리스트 길이에 상관없이 첫 번째 노드 앞이나 마지막 노드 뒤에 일정한 시간으로 노드를 삽입할 수 있다.

(2) 장점

• 어느 한 노드로부터 다른 모든 노드에 접근할 수 있다.
• 임의의 노드 검색 시 첫 노드부터 찾지 않고 현재 노드부터 검색할 수 있다.

(3) 단점

• 노드 검색 시 무한루프에 빠질 수 있다.
• 무한루프 문제는 head포인터를 두어 무한 루프를 방지할 수 있다.

(4) 원형 연결리스트의 앞에 노드 삽입

procedure INSERT(T, Y) /* T(헤드 포인터)는 마지막 노드를 가리킨다. */
/* Y가 지시하는 노드를 원형 리스트의 맨 앞에 삽입 */
① 	if T = nil then T←Y /* 리스트가 빈 상태로 T가 Y를 지시 */
	LINK(Y) ← T /* Y가 지시하는 노드는 자신을 가리킨다. */
②	else LINK(Y)←LINK(T) /* 새 리스트가 첫 번째 노드를 지시 */
③	LINK(T)←Y /* 마지막 노드의 링크 필드가 새 노드를 지시 */
end INSERT

```c void insertFront(listPointer last, listPointer node) { /* 리스트의 마지막 노드가 last인 원형 리스트의 앞에 노드를 삽입한다. */ if(!(*last)) { /* 리스트가 공백일 경우, last가 새로운 항목을 가리키도록 변경시킨다. */ *last = node; node→link = node; } else { /* 리스트가 공백이 아닌 경우, 리스트 앞에 새로운 항목을 삽입한다. */ node→link = (*last)→link; (*last)→link = node; } } ```

(5) 원형 연결리스트의 맨 뒤에 노드

procedure INSERT(T, Y) /* T(헤드 포인터)는 마지막 노드를 가리킨다. */
/* Y가 지시하는 노드를 원형 리스트의 맨 뒤에 삽입 */
if 	T = nil then T←Y /* T가 Y를 가리킨다. */
	LINK(Y)←T /* 리스트가 빈 상태로 Y가 자신을 지시 */
① else LINK(Y)←LINK(T) /* 새 리스트가 첫 번째 노드를 지시 */
② LINK(T)←Y /* 마지막 노드의 링크 필드가 새 노드를 지시 */
③ T←Y /* T가 Y를 가리킨다 */
end INSERT

void insertFront(listPointer last, listPointer node)
{	/* 리스트의 마지막 노드가 last인 원형리스트의 뒤에 노드를 삽입한다. */
	if (!last) {	/* 리스트가 공백일 경우, last가 새로운 항목을 가리키도록 변경시킨다. */
    	last = node;
        node→link = node;
    ]
    else { /* 리스트가 공백이 아닌 경우, 리스트의 뒤에 새로운 항목을 삽입한다. */
    	node→link = last→link;
        last→link = node;
        last = node;
    }
}

(6) 원형 연결 리스트의 전체 삭제

void cerase(polyPointer ptr)
{ /* ptr이 가리키는 원형 리스트 삭제 */
	polyPointer temp;
    if(ptr) {
    	temp = ptr→link; /* ① */
        ptr→link = avail; /* ② avail은 가용공간 리스트 */
        avail = temp; /* ③ */
        ptr = NULL;
    }
}