[DB-23] 자료구조 - 리스트(List)

1. 리스트의 종류

• 선형 리스트 : 연속적 -> Array(배열)
• 연결 리스트 : 비연속적 -> 포인터

2. 선형 리스트(Linear List)

• 연속적인 기억 장소에 저장된 리스트, 순차 리스트 또는 연결 리스트(Dense List)라고 함
• 형태 : 임의의 노드에 접근을 할 때는 인덱스를 사용하므로 포인터가 없음

3. 선형 리스트 장점

• 간단한 자료구조
• 저장 효율이 뛰어남 (기록밀도 : 1 )
• 접근 속도(Access Time)가 빠름

4. 선형 리스트 단점

• 삽입과 삭제가 어려움, 삽입 및 삭제 시 삽입하거나 삭제할 위치 이후의 모든 자료의 이동이 필요

5. 연결 리스트(linked list)

• 자료들을 임의의 기억공간에 기억시키고, 자료 항목의 순서에 따라 노드의 포인터 부분을 이용하여 서로 연결시킨 자료구조
• 각 노드는 다음 노드를 가리키는 링크(Link, Pointer) 정보를 가짐
• 마지막 노드는 포인터 정보를 Null 값을 가짐

6. 연결 리스트 장점

• 자료의 삽입 및 삭제가 용이
• 비연속적 (한 리스트를 여러 개의 리스트로 분리하기 쉬움)
• 희소 행렬(행렬의 요소들 중에서 많은 부분이 0으로 되어 있는 행렬)을 연결 리스트로 표현 시 기억 장소 이용효율이 좋음

7. 연결 리스트 단점

• Access Time이 느림
• 기억 장소 이용 효율이 나쁨 (저장되지 않은 빈 공간 발생)
• 포인터를 위한 추가 공간이 필요
• 중간 노드 연결이 끊어지면 그다음 노드를 찾기 힘듦

8. 연결 리스트 종류

• 단순 연결 리스트 (단순 링크드 리스트)
• 이중 연결 리스트
• 단순 환형 연결 리스트