- 순서를 가진 데이터의 집합을 가리키는 추상자료형
- 동일한 데이터를 가지고 있어도 상관 없음
- 구현방법에 따라 크게 두 가지로 나뉜다
- 순차 리스트 : 배열을 기반으로 구현된 리스트
- 연결 리스트 : 메모리의 동적할당을 기반으로 구현된 리스트
- 1차원 배열에 항목들을 순서대로 저장
- 데이터의 종류와 구조에 따라 구조화된 자료구조를 만들어 배열에 저장할 수도 있음
int[] L = {4, 9, 11, 23};
- 배열의 인덱스를 이용해 원하는 위치의 데이터에 접근할 수 있음
int a = L[0]; // L[0] = 4
- 자료의 삽입/삭제 연산 과정에서 연속적인 메모리 배열을 위해 원소들을 이동시키는 작업이 필요
- 원소의 개수가 많고 삽입/삭제 연산이 빈번하게 일어날수록 작업에 소요되는 시간이 크게 증가
- 배열의 크기가 정해져 있는 경우, 실제로 사용될 메모리보다 크게 할당하여 메모리의 낭비를 초래할 수 도 있고 반대로 할당된 메모리보다 많은 자료를 사용하여 새롭게 배열을 만들어 작업을 해야하는 경우가 발생할 수도 있음
- 자료의 논리적인 순서와 메모리 상의 물리적인 순서가 일치하지 않고, 개별적으로 위치하고 있는 각 원소를 연결하여 하나의 전체적인 자료구조를 이룬다.
- 링크를 통해 원소에 접근하므로, 순차 리스트에서처럼 물리적인 순서를 맞추기 위한 작업이 필요하지 않다.
- 자료구조의 크기를 동적으로 조정할 수 있어, 메모리의 효율적인 사용이 가능하다.
- 노드
- 연결 리스트에서 하나의 원소르 ㄹ표현하는 building block
- 구성 요소
- 데이터 필드
- 원소의 값을 저장
- 저장할 원소의 종류나 크기에 따라 구조를 정의하여 사용
- 링크 필드
- 헤드
- 연결 리스트의 첫 노드에 대한 참조값을 가지고 있음
- 노드가 하나의 링크 필드에 의해 다음 노드와 연결되는 구조를 가진다.
- 헤드가 가장 앞의 노드를 가리키고, 링크 필드가 연속적으로 다음 노드를 가리킨다.
- 링크 필드가 Null인 노드가 연결 리스트의 가장 마지막 노드이다.
- 첫번째 노드로 삽입
- 새로운 노드를 생성
- 새로운 노드의 데이터 필드에 값 저장
- Head에 저장된 참조값을 새로운 노드의 링크 필드값에 저장
- Head에 새로운 노드의 참조값을 저장
- 마지막 노드로 삽입
- 새로운 노드 생성
- 새로운 노드의 데이터 필드에 값을 저장, 링크 필드에는 Null 저장
- 리스트 마지막 노드의 링크 필드에 새로운 노드의 참조값을 저장
- 가운데 노드로 삽입 (A,B,C가 담겨진 리스트의 두번째에 D를 삽입)
- 새로우 노드 생성
- 새로우 노드의 데이터 필드에 D 저장
- 삽입될 위치의 바로 앞에 위치한 노드의 링크 필드를 새로운 노드의 링크 필드에 복사
- 새로운 노드의 참조값을 바로 앞 노드의 링크필드에 저장
- A,C,D를 원소로 가지고 있는 리스트의 A노드를 삭제
- 삭제할 노드의 앞 노드 탐색
- A가 가장 앞 노드이기 때문에 선행 노드 없음
- 삭제할 노드의 링크 필드를 리스트의 Head에 복사
- 삭제할 노드의 링크 필드에 Null 저장
- A,B,C,D를 원소로 가지고 있는 리스트의 B 노드 삭제
- 삭제할 노드의 앞 노드 탐색
- 삭제할 노드의 링크 필드를 선행 노드의 링크 필드에 복사
- 삭제할 노드의 링크 필드에 Null 저장
- 양쪽 방향으로 순회할 수 있도록 노드를 연결한 리스트
- 두 개의 링크 필드와 한 개의 데이터 필드로 구성
- 이전 노드와 다음 노드의 참조값을 각각의 링크 필드에 저장
- cur이 가리키는 노드 다음으로 D값을 가지는 노드를 삽입
- 새로운 노드를 생성하고 데이터 필드에 D를 저장
- cur노드의 next를 새로운 노드의 next에 저장
- cur의 참조값을 새로운 노드의 prev에 저장
- 새로운 노드의 참조값을 이전 노드의 next에 저장
- 새로운 노드의 참조값을 다음 노드의 prev에 저장
- cur이 가리키는 노드를 삭제하는 과정
- 삭제할 노드 cur의 next를 이전 노드의 next에 저장
- 삭제할 노드 cur의 prev를 다음 노드의 prev에 저장
- cur의 prev와 next에 null 저장