[알고리즘] 연결 리스트의 개념 및 기본 (단순연결리스트의 삽입연산, 삭제연산)

연결리스트

 데이터와 링크를 저장하는 노드를 이용하여 기차처럼 노드를 연결시켜 데이터를 저장하는 것이다. 리스트의 항목들을 노드라고 하는 곳에 분산하여 저장한다. 노드의 구조는 데이터필드, 링크필드로 구성되어있다. 

• 데이터필드: 리스트의 원소, 즉 데이터 값을 저장하는 장소
• 링크필드: 다른 노드의 주소값을 저장하는 장소

연결 리스트의 장점

• 삽입, 삭제가 용이하다.
• 연속된 메모리 공간이 필요 없다.
• 크기 제한이 없다.

연결 리스트의 단점

• 구현이 복잡하다.
• 오류가 발생하기 쉽다.

 

연결 리스트의 구조

• 노드: 데이터필드 + 링크 필드
• 헤드 포인터: 리스트의 첫번째 노드를 가리키는 변수

 

연결 리스트의 종류

• 단순 연결 리스트

  

• 원형 연결 리스트

• 이중 연결 리스트

단순 연결리스트의 개념

• 하나의 링크 필드를 이용하여 연결한다.
• 마지막 노드의 링크 값은 NULL이다.

단순 연결 리스트의 구현

typedef int element;
typedef struct ListNode{
    element data;
    struct ListNode *link;
}ListNode;

• 데이터 필드: 구조체로 정의
• 링크 필드: 포인터 사용
• 노드의 구조를 구초제를 이용하여 정의하였지만 아직 노드가 생성되지 않았음에 주의해야 한다.
  • ListNode는 노드를 만들기 위한 설계도에 해당한다.

 

• 노드의 생성하기 위해 동적 메모리 생성 라이브러리 malloc() 함수를 이용한다.

ListNode p1;
p1=(ListNode *)malloc(sizeof(ListNode));

위처럼 코드를 작성하면 p1이라는 노드가 생성된 것이다.

 

 

• 이제 노드가 생성되었으니 데이터 필드와 링크 필드를 설정해주어야 한다.

p1 -> data = 10;
p1 -> link = NULL;

 

• 첫번째 노드에 대한 세팅이 끝났다. 이제 두번째 노드를 생성하고 첫번째 노드와 연결해보자.

ListNode *p2;
p2 = (ListNode*)malloc(sizeof(ListNode));
p2->data = 20;
p2->lint = NULL;
p1->link = p2;

• 헤드 포인터: 연결 리스트의 맨 처음 노드를 가리키는 포인터이다.
• 주의점: 동적 메모리 할당을 이용했기 때문에 사용이 끝나면 반드시 메모리 해제가 필요하다!(중요)

free(p1);
free(p2);

 

단순 연결 리스트 삽입 연산

• before 노드와 after 노드 중간에 new 노드를 삽입하고자 한다.
• 삽입하고자 하는 노드인 new 노드가 after 노드를 가리키게 해야 한다.
• before 노드의 링크 필드에 after 노드의 포인터가 들어있으므로 before 노드의 링크를 new노드의 링크로 복사한다.
• 그 후 before 노드의 링크 필드가 new를 가리키게 한다. 

• 삽입 함수의 프로토 타입

void insert_node(ListNode **phead, ListNode *p, ListNode *new_node)

헤드 포인터가 함수 안에서 변경될 수 있으므로 헤드포인터의 포인터가 필요하다. p는 삽입될 위치의 선행노드를 가리킨다. p가 가리키는 노드의 다음에 삽입된다.

 

• 삽입의 3가지 경우
  1. head가 NULL인 경우: 공백 리스트에 삽입 
     • head값만 변경하면 된다.
  2. p가 NULL인 경우
     • 새로운 노드를 리스트 맨 앞에 삽입한다.
  3. head와 p가 NULL이 아닐 경우
     • 가장 일반적인 경우
     • new_node의 링크 필드에 p->link 값을 복사한 다음
     • p->link가 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){
        new_node->link = *phead;
        *phead = new_node;
    }
    else{
        new_node->link = p->link;
        p->link = new_node;
    }
}

 

 

단순 연결 리스트 삭제 연산

• before 노드와 after 노드 중간에 removed 노드를 삭제하고자 한다.
• before 노드의 링크필드가 after 노드를 가리키도록 변경하면 된다.
• after 노드를 가리키는 포인터는 removed 노드의 링크필드에 있으므로 removed 노드의 링크 필드를 before 노드의 링크 필드로 복사한다. 

 

• 삭제 함수의 프로토 타입

void remove_node(ListNode **phead, ListNode *p, ListNode *removed)

//phead: 헤드 포인터 head에 대한 포인터
//p: 삭제할 노드의 선행 노드를 가리키는 포인터 (before노드의 역할을 한다.)
//removed: 삭제할 노드를 가리키는 포인터

 

• 삭제의 2가지 경우
  1. p가 NULL일 경우 -> 맨 앞의 노드를 삭제
     • head 포인터를 변경한다.
  2. p가 NULL이 아닐 경우 -> 중간 노드를 삭제
     • removed 앞에 노드인 p의 링크를 removed 다음 노드를 가리키도록 변경

 

삭제 연산의 코드

void remove_node (ListNode **phead, ListNode *p, ListNode *removed){
    if (p == NULL){
        *phead = (*phead)->link;
    }
    else{
        p->link = removed->link;
    }
    free(removed);
}