☑️ 연결리스트 개념
- 정의
- 하나의 링크 필드를 가진 노드들이, 모두 자기 후속 노드와 연결되어 있는 리스트
- 마지막 노드는 리스트 끝을 표시하는
null값을 가짐
- 같은 용어
- 선형 연결 리스트 (linear linked list)
- 단순 연결 선형 리스트 (singly linked linear list)
- 연결 리스트 (linked list)
☑️ 구조체 및 메서드 선언
//매크로함수 실패 시 1, 성공 시 0
#define IS_FULL(ptr) (!(ptr))
#define IS_EMPTY(ptr) (!(ptr))
//타입선언
typedef struct listNode {
int data;
struct listNode* link;
}list_node;
typedef struct{
listNode* head;
}linkedList_h;☑️ 생성 알고리즘
// 공백 리스트 생성
linkedList_h* createLinkedList_h (void) {
linkedList_h* L;
L = (linkedList_h*)malloc(sizeof(linkedList_h));
L->head = NULL;
return L;
}☑️ 해제 알고리즘
void freeLinkedList_h(linkedList_h* L) {
listNode* p;
while(L->head != NULL){
p = L->head;
L->head = L->head->link;
free(p);
p = NULL;
}
}☑️ 삽입 알고리즘
void insert (listNode* ptr, listNode* node, int x){
// node는 리스트 전체를 의미
// ptr이 가리키는 노드 다음에 삽입함
listNode* newNode;
newNode = (listNode*r) malloc (sizeof(listNode));
newNode.data = x;
// 메모리가 가득 찼다면
if (IS_FULL(newNode)){
fprintf(stderr, "The memory is full\n");
exit(1);
}
// 1. 공백리스트인 경우
if (node == NULL) {
L = newNode;
newNode->link = NULL;
}
// 2. 맨 앞에 삽입하려는 경우
else if (ptr == NULL){
newNode->link = node;
node = newNode;
}
// ptr이 가리키는 노드의 다음 노드로 삽입
else {
newNode->link = ptr->link;
ptr->link = newNode;
}
}- 포인터 변수 ptr이 가리키는 list에서 또 다른 포인터 변수 node가 가리키는 node(값이 x인) 다음에 새로운 node 삽입
- (1)node가 null인 경우, (2)ptr이 null인 경우, (3)node와 ptr이 null이 아닌경우로 나누어 구현
☑️ 마지막 노드 삽입 알고리즘
void addLastNode(linkedList_h* L, int x){
listNode* newNode = (listNode*) malloc (sizeof(listNode));
newNode->data = x;
newNode->link = NULL;
//1. 빈 리스트일 때는, 최초삽입
if (node==NULL) {
L->head = newNode;
return;
}
//2. 노드가 1개 이상일때
listNode* p = L->head; // 임시순환 포인터
while (p->link != NULL){ // 마지막 노드를 찾을 때 까지
p = p->link; // 다음 노드로 이동
}
p->link = newNode; // 마지막에 새로운 노드 삽입
}☑️ 삭제 알고리즘
void delete(list_pointer *ptr, list_pointer trail, list_pointer node){
// *ptr: list 가리키는 포인터
// trail : 삭제할 node의 전 node
// node : 삭제할 node
// trail 존재하면 삭제할 노드 link를 trail.link로 연결
if (node==NULL) { //공백리스트일 경우 에러
exit(1);
}
if (trail){
trail->link = node->link;
} else { // 맨 앞 노드를 삭제할 경우, ptr 전진
//ptr = ptr->link; 도 가능
ptr = node->link;
}
free(node);
}- 변수 ptr이 가리키는 list 내에, 포인터 변수 node가 가리키는 node 삭제
- trail은 변수 node가 가리키는 node의 바로 앞 node를 가리킴 (trail.link == node)
- 맨 앞 node를 삭제할 경우, node=ptr, trail=NULL
☑️ 마지막 노드 삭제 알고리즘
void deleteLastNode(linkedList_h* L){
listNode* previous;
listNode* current;
// 1. L이 공백 리스트인 경우
if(L == NULL) return;
// 2. L에 노드가 1개만 있는 경우
if(L->link == NULL) {
free(L);
L = NULL;
}
// 3. L에 노드가 2개 이상인 경우
else {
previous = L;
current = L->link;
while(current->link != NULL){ // current가 마지막 노드에 도달할 때 까지
previous = current; // current 전 노드를 previous로 저장
current = current.link; // current 한칸 씩 이동
}
free(current); // 마지막 노드를 없앰
previous.link = NULL;
}
}☑️ 역순변환 알고리즘
void reverse(linkedList_h* L){
listNode* lead <- L // lead는 역순으로 변환시킬 리스트
listNode* middle = NULL; // middle은 역순으로 변환될 노드
listNode* trail = NULL; // trail은 역순으로 변환된 노드
while(**lead != null**) {
//trail은 middle을, middle은 lead를 차례로 따라간다
trail = middle;
middle = lead;
lead = lead.link;
// middle의 링크 방향을 역으로 바꿈
**middle.link = trail**;
}
L->head = middle;
}- lead(가장 앞), middle(중간), trail(가장 뒤) 3개의 포인터를 이용하여 처리
- middle이 현재 lead 위치를 지킴 > lead는 앞으로 전진 > middle의 링크 방향을 역으로 바꿈
☑️ 연결리스트 출력 알고리즘
void printList(linkedList_h* L){
listNode* p;
p = L.head;
printf("(");
while(p != NULL) {
printf("%d", p.data);
p=p.link; //다음 노드로 이동
if(p!=NULL) printf(", ");
}
printf(")\n");
}☑️ main 함수
int main(){
//공백리스트 생성
linkedList_h* L;
L = createLinkedList_h();
//data 삽입
addLastNode(L, 1);
addLastNode(L, 2);
addLastNode(L, 3);
//data 삭제
deleteLastNode(L);
//역순으로 변환
reverse(L);
printList(L);
}
👩💻 IT Engineering