자료구조 - 리스트

리스트는 자료구조에서도 다른 자료구조를 구현하는데 기반이 되는 선형 자료구조이자 추상적 자료형이다. 

 

리스트는 크게 다음과 같이 배열로 구현된 순차리스트, 연결 리스트로 구현된 연결리스트로 나뉜다. 

 

 

순차 리스트는 단순 배열로 구현된 리스트로 어느 위치에서든 입출력 가능하다. 

 

 

하지만 위와 같이 밀어내는 연산을 해야하며 마찬가지로 삭제 시에도 동일한 연산을 수행하며 추가 연산 시간이 소모된다. 

 

 

연결 리스트는 순차 리스트와 다르게 입출력 시 추가 연산을 소모하지 않는다 대신 원소들을 탐색하는 과정에서 인덱스를 명시해 빠르게 출력하지 않고 아래와 같이 타고 들어가 직접 원소를 찾는 추가 작업을 진행한다.  

 

 

연결 리스트는 그림과 같이 노드라고 불리는 데이터 덩어리를 1개의 원소를 가지며 노드는 입력된 데이터인 데이터 필드, 다음 노드를 가르키는 링크 필드로 나뉜다. 위에 연결 리스트는 단순 선형 연결 리스트로 마지막은 Null 을 가르키며 특정 노드를 탐색하지 못하는 경우가 발생할 수 있다. 

 

 

원형 리스트는 마지막 노드가 Null 이 아닌 가장 앞의 Head 를 가르키는 연결리스트로 시간이 조금 걸리더라도 하나의 노드에서 다른 모든 노드로 접근이 가능하다. 원형 큐의 구현 기반이 되는 자료구조다.

 

마지막으로 덱의 기반이 되는 이중 연결 리스트는 다음과 같이 이루어져 있다. 

 

 

이중 연결 리스트는 기존의 노드와 다르게 두 방향의 링크 필드를 가지고 있으며 그로인해 양방향으로 접근이 가능하다. 따라서 양쪽에서 입출력을 하는 덱을 구현할 수 있으며 구현하기 까다롭지만 어차피 우리는 이미 만들어진 클래스를 사용한다 셋 중에 가장 유용한 자료구조라고 생각한다.