2.3 리스트

2.3.1 리스트의 개념
리스트[선형 리스트(linear list) 또는 순서 리스트(ordered list)]는 1개 이상의 원소들이 순서를 가지고 구성됨.

선형 리스트는 A=(a1, a2,…, ai,…, an), i= i번째 원소, n=리스트의 크기.
예) •요일 리스트: (월, 화, 수, 목, 금, 토, 일)
• 전쟁 리스트: ((황산벌 전투, 660), (임진왜란, 1592), (제1차 세계대전,1914), (제2차세계대전, 1939))

2.3.2 리스트의 구현
리스트를 표현하는 가장 간단한 방법 - 1차원 배열 이용.
선형 리스트와 1차원 배열 - 순차적인 구조.
리스트의 논리적인 순서 = 배열의 물리적인 저장 순서.

리스트에 원소를 삽입하기 위해서는 원소를 삽입할 위치에 있는 원소와 그 다음의 원소들을 모두 한 칸씩 뒤로 이동. 배열로 표현된 리스트의 원소를 삭제하기 위해서는 삭제할 원소를 찾아 삭제한 후에, 그 뒤에 있는 모든 원소를 한칸씩 앞으로 이동.(삽입 연산과 삭제 연산을 수행하기 위해서는 원소들의 자리 이동이 발생.)
-> 빈번한 자료 이동으로 인한 비효율적인 컴퓨팅 성능 문제.

* 연결 리스트(linked list) - 노드 간의 포인터 연결을 통
해서 구현되며, 각 노드는 적어도 두 종류의 필드, 원소값을 저장하는 데이터 필드와 노드 연결을 위한 링크 필드.
- 데이터 필드는 리스트의 원소값을 저장하기 위한 부분.
- 링크 필드는 리스트에서 순서상 다음에 오는 원소가 저장되어 있는 노드 주소를 저장.

• 포인터 변수 head는 연결 리스트의 시작 노드.
• 마지막 노드를 제외한 나머지 모든 노드의 링크는 논리적으로 바로 다음에 위치하는 노드를 가리키는 주소.
• 마지막 노드의 링크는 더 이상 가리킬 것이 없는 널(null) 포인터.

연결 리스트는 리스트 원소의 논리적 순서만을 지원. 실제로 연결 리스트 원소의 저장 순서는 순차적이지 않음.

연결리스트는 선형리스트의 원소의 순서와는 다르게 컴퓨터 메모리에 저장.

* 단일 연결 리스트(singly linked list)
노드의 링크 필드가 하나이고, 후행 노드만를 가리킴. 따라서 특정 노드의 후행 노드는 쉽게 접근할 수 있지만, 선행 노드에 대한 접근은 헤드 노드부터 새로 시작해야 함.

* 이중 연결 리스트(doubly linked list) 단일
단일 연결 리스트의 단점을 보완하기 위해 노드가 2개의 링크 필드를 가짐. 즉, 특정 노드의 하나의 링크는 후행 노드를 가리키고, 다른 하나의 링크는 선행 노드를 가리킴. >> 특정 노드에서 후행 노드뿐만 아니라 선행 노드에 대한 접근을 쉽게 제공하기 위한 것