1. 연결 리스트의 변형
1.1. 단순 연결 리스트
•
하나의 링크만 존재
•
각각의 노드 링크는 후행 노드만을 가리키는 구조
•
이슈
◦
특정 노드의 후행 노드 접근은 쉬움
◦
그러나, 특정 노드의 선행노드에 대한 접근은 헤드 노드로부터 재 검색해야하는 문제 발생
1.2. 이중 연결 리스트
•
2개의 링크를 가짐
◦
선행노드를 가리키는 링크
◦
후행 노드를 가리키는 링크
•
특정 노드에서 선행/후행 노드에 간단한 프로그램 코드를 통해 접근 가능
1.3. 원형 연결 리스트
•
리스트의 마지막 원소 뒤에는 아무 원소도 없음
•
따라서, 연결 리스트는 가장 마지막 노드의 링크 필드는 항상 null임
•
마지막 노드의 링크 필드를 활용하면서 프로그램 성능에 도움되기 위해 원형 연결 리스트가 제안됨
2. 원형 연결 리스트
2.1. 원형 연결 리스트의 생성
•
예시
•
정의 및 생성
typedef struct ListNode { //원형 연결 리스트의 노드 구조 정의
int data;
struct ListNode* link;
} listNode;
typedef struct { //원형 연결 리스트의 헤드 노드 구조 정의
ListNode* head;
} linkedList_h;
linkedList_h* createLinkedList_h(void){ // 원형 연결 리스트의 헤드 노드 생성
linkedList_h* H;
H = (inkedList_h*)malloc(sizeof(inkedList_h));
H -> head = NULL:
return H;
}
C
복사
2.2. 삽입 연산
•
삽입 연산 1
void addFirstNode(inkedList_h*H, int x){
// 원형 리스트 첫번째 노드 삽입 연산, x값은 100이라 가정함
listNode* tempNode;
listNode* NewNode;
NewNode = (listNode*)malloc(sizeof(listNode));
NewNode -> data = x;
NewNode -> link = NULL;
}
C
복사
•
삽입 연산 2
void addFirstNode(inkedList_h*H, int x){
if(H -> head == NULL) { //현재 리스트가 공백인 경우
H -> head = NewNode;
NewNode -> link = NewNode;
}
tempNode = H -> head;
while(tempNode -> link != H -> head)
tempNode = tempNode -> link;
NewNode -> link = tempNode -> link;
tempNode -> link = NewNode;
H -> head = NewNode;
}
C
복사
•
예시
3. 이중 연결 리스트
•
단순 연결리스트의 단점
◦
어떤 특정노드의 선행 노드를 찾기가 어려움
•
이중 연결 리스트
•
원형 이중 연결 리스트
•
이중 연결 리스트의 노드 구조
◦
양쪽 방향으로 순회할 수 있도록 링크 필드가 2개 필요
◦
시작점(head)도 두개의 링크가 필요
◦
이중 연결 리스트의 노드 구조
▪
2개의 링크 필드와 1개의 데이터 필드
•
Llink / data / Rlink
•
초기화
typedef struct ListNode{
// 이중 연결 리스트의 노드 구조 정의
struct ListNode* Llink*
int data;
struct ListNode* Rlink*
} listNode;
typedef struct {
// 이중 연결 리스트의 헤드 노드 구조 정의
listNode* Lhead*
listNode* Fhead* //Rhead
} linkedList_h;
linkedList_h* createLinkedList_h(void){
// 원형 연결 리스트의 헤드 노드 생성
linkedList_h* H;
H = (linkedList_h*)malloc(sizeof(linkedList_h));
H -> Lhead = NULL;
H -> Fhead = NULL;
return H;
}
C
복사
•
이중 연결 리스트
•
이중 연결 리스트의 노드 삽입
•
이중 연결리스트의 노드 삭제
void deleteDNode(linkedList_h* H, listNode* delNode){
// 이중 연결 리스트에서 데이터의 값이 300인 노드(delNode)를 삭제하는 연산
delNode -> Llink -> Rlink = delNode -> Rlink;
delNode -> Rlink -> Llink = delNode -> Llink;
free(delNode)
}
C
복사
