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

리스트 (List)

• 자료를 순서대로 (Sequential) 일직선으로 저장하는 자료구조
• 자료가 일직선으로 서로 연결된 선형구조
• 자료 추가 : 빈 공간 확보를 위해 기존 자료들의 위치 이동
• 자료 삭제 : 빈 공간이 없도록 함

 

1. 배열 리스트 (Array List)

• 배열은 메모리 상에 순차적 (Sequential)으로 저장됨
• 논리적 순서 = 물리적 순서
• 원소 추가 : 맨 뒤 index ~ 추가하려는 index 까지의 원소들을 뒤로 한 칸씩 이동시킨다. (공백 추가)
• 원소 삭제 : 삭제 index ~ 맨 뒤 index 까지의 원소들을 앞으로 한 칸씩 이동시킨다. (공백 제거)

배열 리스트

 

2. 연결 리스트 (Linked List)

• 포인터를 이용하여 리스트를 구현 → 물리적으로 멀리 떨어진 자료들을 순서대로 연결
• 논리적 순서 ≠ 물리적 순서
• 자료 (Data), 링크 (Link), 노드 (Node) 로 구성
• 노드 추가 : 앞 노드 링크 → 추가 노드, 추가 노드 링크 → 뒷 노드에 연결한다.
• 노드 삭제 : 앞 노드 링크 → 뒷 노드에 연결한다.

연결 리스트

 

구분	배열 리스트	연결 리스트
설명	논리적 저장순서, 물리적 저장순서 순차적	논리적 저장순서만 순차적
구현 방식	배열 (Array)	포인터 (Pointer)
구현 복잡도	낮음	높음
원소 접근속도	빠름	느림
기타	- 추가 / 삭제 시 원소 이동 필요 - 최대 저장 원소개수 지정 필요	- 추가 / 삭제 시 원소 이동 필요 없음 - 최대 저장 원소개수 지정 필요 없음