All
리스트의 개념
•
리스트(List)는 원소들이 일정한 순서로 나열된 자료구조
•
리스트의 순서
◦
물리적 순서: 실제 메모리 상에서 원소들이 저장된 위치의 순서
◦
논리적 순서: 사람이 이해하는 의미적 흐름이나, 정의에 의해 결정된 순서
즉, 리스트는 단순히 데이터를 모아둔 것이 아니라, 원소 간의 순서 관계가 중요한 구조
배열의 이용한 리스트의 구현
배열
•
배열은 메모리 상에서 원소들이 연속된 공간에 저장됨
•
인덱스를 사용해 원하는 위치의 원소를 O(1) 시간에 접근 가능
◦
예 AAA[3] → 3번째 원소 바로 찾을 수 있음
배열의 확장 문제
•
배열은 선언 시점에 크기를 고정
•
프로그램 실행 중 크기를 늘리고 싶다면 새로운 배열을 생성해 데이터를 복사해야 함
•
이를 피하기 위해 처음부터 넉넉하게 잡으면 → 사용하지 않는 공간이 발생하여 메모리 낭비
원소 삽입(삭제)시 문제
•
리스트의 맨 끝에 삽입하는 경우는 단순히 인덱스를 증가시키면 되므로 효율적임
•
하지만 리스트 중간에 삽입하려면?
◦
삽입 위치 이후의 모든 원소를 한 칸씩 뒤로 이동해야 함
◦
예: 1000개의 원소 중 2번째 위치에 삽입 → 999개를 뒤로 이동해야 함
•
원소가 많을수록 이동 횟수가 커져 → 삽입 시간 증가
•
삭제 시도 마찬가지로 원소를 삭제하면 뒤에 있는 원소들 앞으로 한칸씩 당겨와야함
포인터를 이용한 리스트의 구현
노드의 구조
•
연결 리스트의 기본 단위는 노드(node)
•
노드는 두 부분으로 구성됨
◦
데이터(Data): 리스트의 실제 원소 값
◦
포인터(Link): 다음 노드의 메모리 주소(위치)
•
각 노드는 자기 뒤에 어떤 노드가 오는지 가리킴
struct linked_list_node {
int data;
struct linked_list_node *link;
};
C
복사
노드의 연결
•
연결 리스트는 Head 포인터에서 시작
•
Head는 첫 번째 노드를 가리킴
•
각 노드는 다음 노드를 포인터로 연결 → 마지막 노드는 Null
•
물리적으로 메모리 여기저기에 흩어져 있어도, 포인터 연결을 통해 논리적 순서 유지 가능
연결리스트 삽입과 삭제
원소 삽입
•
배열과 달리, 원소 이동 없이 포인터만 변경해서 삽입 가능
•
삽입 과정
1.
새 노드를 만들고 데이터 저장
2.
새 노드의 포인터가 삽입 위치 뒤 노드를 가리키게 함
3.
삽입 위치 앞 노드의 포인터를 새 노드를 가리키도록 변경
초기 연결리스트
x 삽입
원소 삭제
•
삭제도 마찬가지로 원소 이동 없이 포인터만 조정
•
삭제 과정
1.
삭제할 노드를 찾음
2.
삭제할 노드의 이전 노드 포인터를 → 삭제할 노드의 다음 노드를 가리키도록 변경
3.
삭제할 노드 메모리를 해제
초기 연결리스트
삭제 후 노드 포인터 변경