리스트
리스트의 개념
- 물리적인 저장 위치와 상관 없이 “논리적인 순서”로 연결된 순서 리스트
- 배열의 인덱스로 표현되는 추상적인 순서가 원소간 실제 물리적인 위치의 관계가 있다면,
- 리스트는 인덱스로 표현되는 추상적인 순서가 실제 물리적인 위치와 관계가 없다.
- 배열 기반으로 구현된 그냥 리스트와, 포인터로 구현된 연결리스트(linked list)가 있다.
배열 기반 리스트와 연결리스트의 비교
| 구분 | 배열 기반 리스트 | 연결리스트 |
|---|---|---|
| 구현 방법 | - 배열을 이용. 배열과 동일함. | -포인터를 이용해 원소값을 저장하는 공간과 다음 원소를 가리키는 위치 정보를 저장하는 공간을 함께 구현하는 방법 |
| 메모리 배치 | - 연속적인 메모리(저장위치) | - 비연속적인 메모리 |
| 데이터 접근 | 빠름 (O(1)) | 느림 (O(n)) |
| 삽입/삭제 | 느림 (O(n), 데이터 이동 필요) | 빠름 (O(1), 포인터만 수정) |
| 크기 | 고정 크기(언어에 따라 다름) | 동적 크기 |
| 추가적인 메모리 사용 | 없음 | 포인터 공간 필요 |
| 구현 복잡도 | 간단 | 상대적으로 복잡 |
배열을 이용한 리스트의 비효율성
(1) 리스트의 크기를 조정할 수 없음
크기를 동적으로 조절할 수 없는 배열을 기반으로 구성되었기 빼문에 객체 생성 이후 크기 조정이 어렵다.
-> 초기 배열을 크게 만들면 메모리의 낭비
-> 초기 배열을 충분히 크게 만들지 않으면 배열을 재생성해야하는 번거로움
(2) 원소를 중간에 삽입할 때 많은 연산량
n개의 원소를 가진 배열 기반의 리스트가 있을 때, 리스트의 x번째에 원소를 끼워 넣기 위해서는 (n-x+1) 번 원소를 이동하는 사전 작업이 필요하다. 예를 들어, 500개의 원소를 가진 리스트에서 2번째에 원소를 끼워넣기 위해서는 그 뒤의 199개의 원소를 뒤로 미뤄야 한다. 이는 배열이라는 자료구조의 특성상 논리적 순서와 물리적 저장 순서가 일치해야 함에서 기인하는 문제이다.
(3) 원소의 삭제가 일어날 때 많은 연산량
삽입과 동일하게, 중간에 있는 원소가 삭제될 때에도 그 뒤의 원소들을 앞으로 이동시키는 연산이 필요하다. 이 또한 배열이라는 자료구조의 특성상 논리적 순서와 물리적 저장 순서가 일치해야 함에서 기인하는 문제이다.
이와 같은 배열 기반 리스트는 실제 IT 환경에서는 서비스하기 어려울 정도의 비효율성을 발생시키므로, 실제 잘 사용되지는 않는다.
연결 리스트 - 포인터를 이용한 리스트의 구현
노드의 개념
- 노드 : 리스트의 원소값(데이터)과 다음 노드를 지시하는 포인터(주소 = link)로 구성된 연결리스트의 구성요소
- 포인터 : 메모리 주소를 저장하는 변수로, 연결리스트에서는 다음 노드를 가리키는 도구. 링크(link) 라고도 부른다.
- 포인터를 이용해 연결되었으므로 linked list 즉, 연결 리스트라고 부르는 것이다.
- 마지막 노드의 포인터는 NULL 이다.
헤드의 개념
- 헤드는 리스트의 시작 노드를 가리키는 포인터 변수이다.
포인터를 이용한 리스트의 구현
포인터 변수
1
2
3
4
5
6
7
8
9
10
11
12
13
// 포인터 변수는 * 과 & 두 가지 특수문자만 알면 된다.
1. *
*은 크게 두 가지 의미로 사용된다.
(1) 포인터 변수 선언
- 이 변수는 포인터입니다. 라는 뜻
- ex. int *ptr;
(2) 역참조 연산자로서의 *
- 포인터가 가리키는 주소에 있는 실제 값에 접근하는 역할
- *ptr = 20; : ptr이 가리키는 주소에 20이라는 값을 적재하라.
2. &
&은 변수의 주소를 가져오는 연산자라는 하나의 의미로 사용된다.
연결 리스트의 삽입과 삭제 연산
1. 삭제 연산
Y 노드 = 삭제될 노드 라고 할 때
(1) 삭제될 Y 노드의 선행 노드를 찾고, 이를 X 노드라고 정의한다.
(2) 삭제될 Y 노드의 후행 노드를 찾고, 이를 Z 노드라고 정의한다.
(3) X 노드의 링크 부분이 Z 노드의 후행 노드를 가리키게 한다.
(4) 삭제할 노드를 메모리에 반환한다.
2. 삽입 연산
Y 노드 = 삽입될 노드 라고 할 때
(1) 메모리 공간을 할당받고, 삽입할 내용을 저장하여 Y 노드를 생성한다.
(2) Y 노드의 삽입으로, Y 노드의 선행 노드가 될 노드를 X 노드, Y 노드의 후행 노드가 될 노드를 Z 노드라고 정의한다.
(3) Y 노드의 링크 부분이 Z 노드를 가리키게 한다.
(4) X 노드의 링크 부분이 Y 노드를 가리키게 한다.