leehyeon-dv 님의 블로그
선형리스트 본문
🔑Table of Contents
- 선형리스트 란?
- 선형리스트의 연산
- 배열 - 선형리스트 표현1
📌선형리스트 란?
선형 리스트(혹은 리스트)는 자료가 순서를 가지고 나열된 자료구조
리스트의 원소 = 리스트를 이루고 있는 각각의 자료
n개의 원소 a₀, a₁, ... , aₙ₋₁로 이루어진 리스트는
( a₀, a₁, ... , aₙ₋₁ )로 표기한다
📌선형리스트의 연산
리스트에서 수행하는 대표적인 연산
- 리스트 길이는?
- 리스트의 모든 원소를 하나씩 읽어라
- k번째 원소는 무엇인가
- k번째 원소를 다른 원소로 교체해라
- k번째 위치에 새로운 원소를 삽입하라, 연산을 수행한 후에는 기존의 k번째 원소가 k+1번째 원소가 된다
- k번째 원소를 삭제해라. 기존의 k+1번째 원소가 k번째 원소가 된다
📌배열 - 선형리스트 표현1
이 방식은 리스트의 원소 aₖ를 배열의 k번째 원소에 대응시키는 것이다
배열이 메모리의 연속적인 공간을 차지하므로 순차 매핑이라고 한다
리스트에서 사용되는 연산은 배열을 이용한 표현에서 어떻게 구현될 수 있을까?
• A[k]를 읽거나 교체하는 연산은 상수 시간에 실행할 수 있지만
삽입과 삭제 연산인 경우는 순차 매핑의 성질을 유지하기 위해 원소의 이동이 필요해 더 많은 시간이 소요된다
📌배열 - 선형리스트 표현2
연결 리스트는 화살표로 표시되는 링크를 가진 노드의 순서리스트이다
연결 리스트의 이름 = 첫번째 노드를 가리키는 포인터의 이름
연결 리스트의 노드들은 메모리에 순차적으로 놓여있지 않을 수 있음
📌연결 리스트에서 삽입과 삭제
선형리스트를 배열보다 연결리스트로 표현했을때 삭제가 더 쉬워지는 이유는?
📌C 언어의 포인터와 동적 메모리 할당
void sample(void)
{
int *pi; //포인터 선언
float *pf;
pi = (int *) malloc(sizeof(int)); //int 크기만큼 메모리를 동적으로 할당하고 그 주소를 pi에 저장
pf = (float *) malloc(sizeof(float));
*pi = 1024; //동적으로 할당된 메모리 공간에 1024를 저장
*pf = 3.14;
printf("an integer = %d, a float = %f\n", *pi, *pf);
free(pi); //할당한 정수 메모리 해제
free(pf);
}
📌연결리스트 생성
typedef struct list_node *list_pointer; // list_node 구조체의 포인터 타입을 list_pointer로 정의
typedef struct list_node {
int data; // 노드가 저장할 데이터
list_pointer link; // 다음 노드를 가리키는 포인터
};
list_pointer ptr = NULL; // 리스트의 시작 포인터를 NULL로 초기화
list_pointer create(void) // 두 개의 노드를 생성하고 연결하는 함수
{
list_pointer first, second;
first = (list_pointer) malloc(sizeof(struct list_node)); // 첫 번째 노드를 위한 메모리 동적 할당
second = (list_pointer) malloc(sizeof(struct list_node));
second->link = NULL; // 두 번째 노드는 마지막이므로 link는 NULL로 설정
second->data = 20; // 두 번째 노드의 데이터 설정
first->link = second; // 첫 번째 노드의 link는 두 번째 노드를 가리킴
first->data = 10; // 첫 번째 노드의 데이터 설정
return first; // 첫 번째 노드(리스트의 시작점)를 반환
}
📌연결 리스트에서 노드삽입
/* insert a new node into the list ptr after node */
void insert(list_pointer *ptr, list_pointer node)
{
list_pointer temp;
// 새로운 노드를 동적으로 할당
temp = (list_pointer) malloc(sizeof(list_node));
if (temp == NULL) { // 메모리 할당 실패 시 에러 메시지 출력 후 종료
fprintf(stderr, "The memory is full\n");
exit(1);
}
temp->data = 50; // 새 노드에 데이터 저장
if (node) { // node가 NULL이 아니면, 특정 노드 뒤에 삽입
temp->link = node->link; // temp는 node 다음 노드를 가리킴
node->link = temp; // node의 다음 노드를 temp로 설정
}
else { // node가 NULL이면, 리스트의 맨 앞에 삽입
temp->link = *ptr; // temp가 현재 리스트의 시작 노드를 가리킴
*ptr = temp; // ptr이 temp를 가리키도록 업데이트 (새 시작 노드)
}
}
📌연결 리스트에서 노드삭제
/* delete node, trail is the preceding node */
void delete(list_pointer *ptr, list_pointer trail, list_pointer node)
{
if (trail)
trail->link = node->link;
else
*ptr = (*ptr)->link;
free(node);
}
📌연결 리스트 출력하기
void print_list(list_pointer ptr)
{
printf("The list contains: ");
while (ptr) {
printf("%d ", ptr->data);
ptr = ptr->link;
}
printf("\n");
}
📌헤드 노드를 가진 연결 리스트
헤드 노드를 연결 리스트에 추가하면 연산을 더 쉽게 구현 가능
해드 노드의 data필드는 보통 리스트 전체에 대한 정보를 가지거나 정보가 없다
연결 리스트에 노드를 삽입하는 함수 insert( )에서 ptr이 NULL이면 ptr 값이 변경되어
이 값을 insert( )를 호출한 함수에게 돌려줘야한다
만약 해드 노드를 가지고 있으면 ptr이 언제나 NULL이 아니기 때문에 그럴 필요가 없다
📌환형 연결 리스트
마지막 노드의 link 필드가 NULL이 아니라 리스트의 맨 앞 노드를 가리키는 연결 리스트를 환형 연결 리스트라고 한다
환형 연결 리스트에서는 마지막 노드의 주소만 알면 처음 노드의 주소를 쉽게 알 수 있다
따라서 마지막 노드의 주소로 그 리스트를 나타내는 것이 일반적이다
📌이중 연결 리스트
이중 연결 리스트의 각 노드는 바로 다음 노드의 주소뿐만 아니라 바로 앞 노드의 주소를 가진다
typedef struct node *node_pointer;
typedef struct node {
node_pointer llink; // 왼쪽 링크 (이전 노드)
int data; // 데이터 필드
node_pointer rlink; // 오른쪽 링크 (다음 노드)
};
📌이중 연결 리스트의 삽입과 삭제
/* insert newnode to the right of node */
void dinsert(node_pointer node, node_pointer newnode)
{
newnode->llink = node; //newnode의 왼쪽 링크는 node를 가리킴
newnode->rlink = node->rlink; //newnode의 오른쪽 링크는 다음 노드를 가리킴
node->rlink->llink = newnode; //node의 다음 노드의 왼쪽 링크를 newnode로 연결
node->rlink = newnode; //node의오른쪽링크를 newnode로 연결
}
/* delete from the doubly linked list */
void ddelete(node_pointer ptr, node_pointer node)
{
if (node == ptr) // 헤드 노드는 삭제하지 못하도록 처리
printf("Deletion of head node not permitted.\n");
else {
node->llink->rlink = node->rlink; // node의 앞 노드의 오른쪽 링크를 node의 다음 노드로 연결
node->rlink->llink = node->llink; // node의 다음 노드의 왼쪽 링크를 node의 앞 노드로 연결
free(node); // node의 메모리를 해제
}
}
