1. 리스트의 개념
1.1. 정의
•
기본 정의
◦
일정한 순서의 나열
◦
어떤 정의에 의해서 결정된 논리적 순서의 나열
1.2. 배열 vs 리스트
•
배열
◦
논리적인 순서와 물리적인 순서(메모리상에 적재되는 순서)가 동일함
◦
인덱스로 표현되는 순서가 배열 원소의 메모리 공간 (주기억장치, DDR)에서의 물리적 위치를 의미함
•
리스트
◦
논리적인 순서와 물리적인 순서가 동일 하지 않음
◦
리스트의 순서는 사람들의 머리속에 인식되는 논리적인 순서
혹은 리스트에 나타나는 원소들의 의미적인 순서를 의미함
◦
원소들의 물리적인 저장 순서나 위치와는 무관하게 원소들간의 논리적인 순서만 유지함
•
비교
◦
좌: 배열 / 우: (순서)리스트
1.3. 리스트의 구현 방법
•
포인터를 이용한 방법
◦
원소값을 저장하는 공간과 다음 원소를 가리키는 위치 정보를 저장하는 공간을 함께 구현하는 방법
◦
예) 연결리스트
•
배열을 이용한 방법
2. 배열을 이용한 리스트의 구현
2.1. 배열의 확장
•
초기 배열 선언에서 충분히 크게 하면 어느정도의 배열 추가 확장을 피할 수 있겠지만, 원소를 리스트 중간에 삽입하기 위해서는 리스트의 원소값을 하나씩 뒤로 밀어야 하는 상황이 발생함
◦
충분히 크게 할 경우 → 메모리 낭비
•
예시
◦
(가정) 역사적 사건을 연도별로 리스트로 정의
◦
초기 리스트
value | 1919 | 1945 | 1950 | 1988 |
index | L[0] | L[1] | L[2] | L[3] |
address | ff00 | ff04 | ff08 | ff12 |
◦
1936을 L[1], L[2] 사이에 삽입하고 싶을 경우, 1945, 1950, 1988은 뒤로 밀려나야함
▪
논리적 순서, 물리적 순서 둘다 변경 필요
value | 1919 | 1936 | 1945 | 1950 | 1988 |
index | L[0] | L[1] | L[2] | L[3] | L[4] |
address | ff00 | ff04 | ff08 | ff12 | ff16 |
◦
What if, 배열의 길이가 10만개, 100만개라면..?
2.2. 배열을 이용한 리스트의 원소 삽입/삭제
•
배열로 구현된 리스트는 원소의 순서가 연속적인 물리적 주소에 저장됨
•
원소를 삽입/삭제하기위해서는 해당 원소의 위치 뒤에 있는 모든 원소를 뒤로 물리거나 앞으로 당겨야함
•
리스트 원소값의 이동은 원소수가 많을수록 프로그램 수행시간을 증가 시킴 → 비효율적인 컴퓨팅 성능
3. 포인터를 이용한 리스트의 구현
3.1. 노드의 구조
•
노드 (node)
◦
리스트의 원소(값) + 다음 원소를 가리키는 정보
•
노드는 데이터 요소(원소, 값)와 리스트의 다음 원소를 지시하는 포인터
(주소, 링크:link)로 구성됨
데이터(값) | 1919 |
포인터(메모리 주소값) | ff00 |
3.2. 노드의 구조 및 연결
•
예시
3.3. 연결 리스트의 논리적 순서와 실제 메모리 표현
•
예시
4. 포인터 변수 및 리스트의 삭제/삽입
4.1. 리스트의 생성
•
정수 값 data와 링크 link로 구성된 노드의 생성
◦
link: 포인터 변수 linked_list_node 의 주소값을 저장
struct linked_list_node {
int data;
struct linked_list_node *link;
}
C
복사
4.2. 포인터의 할당과 반환
•
malloc - memory allocation
int a, *p_a;
float b, *p_b;
p_a = (int*)malloc(sizeof(int)); // 메모리 할당
p_b = (float*)malloc(sizeof(float));
*p_a=10; // p_a가 가리키는 곳에 10 저장 (p_a의 포인터를 따라 메모리에 할당된 곳에 10 저장)
*p_b=3.14; // p_b가 가리키는 곳에 3.14 저장
printf("a is %d, b is %f\n", *p_a, *p_b);
free(p_a);
free(p_b);
C
복사
5. 연결 리스트에서 노드의 삽입과 삭제
5.1. 연결 리스트에서 노드의 삭제
•
원소 삭제 연산 단계
◦
삭제할 노드의 선행 노드의 링크 필드를 삭제할 노드의 후행 노드를 가리키게 한다.
◦
삭제할 노드를 메모리에 반환한다.
•
예시
◦
연결 리스트의 초기 모습
◦
연결리스트의 노드 삭제 → i의 link를 6000으로 변경
◦
결과
5.2. 연결 리스트에서 노드의 삽입
•
삭제의 경우와 로직 유사
•
원소 삽입 연산 단계
◦
메모리 공간을 할당받고 삽입할 내용을 저장하여 삽입할 x 노드를 생성
◦
x 노드의 링크부분을 후행 노드가 될 j 노드를 가리키게 함
◦
삽입될 x 노드의 선행 노드가 될 i 노드의 링크 필드가 x 노드를 가리키게 함
5.3. 삽입 연산 코드
•
연결 리스트의 마지막에 삽입 연산
void addNode(linkedList_h* H, int x){
// 리스트의 마지막 노드에 삽입 연산하며, x값을 100이라고 가정함
listNode* NewNode;
listNode* LastNode;
NewNode = (listNode*)malloc(sizeof(listNode));
NewNode -> data = x;
NewNode -> link = NULL;
if (H -> head == NULL) { // 현재 리스트가 공백인 경우
H -> head = NewNode;
return
}
LastNode = H -> head;
while(LastNode -> link != NULL)
LastNode = LastNode -> link;
LastNode -> link = NewNode;
}
C
복사
typedef struct ListNode { // 단순 연결 리스트의 노드 구조 정의
int data[10];
struct ListNode* link;
} listNode;
typedef struct { // 리스트의 헤드(first) 노드 구조 정의
listNode* head;
} linkedList_h;
linkedList_h* createLinkedList_h(void) { // 연결리스트 생성
linkedList_h* H;
H = (linkedList_h*)malloc(sizeof(linkedList_h));
H → head = NULL;
return H;
}
C
복사