[자료구조] 리스트

오늘은 자료구조의 기본 내용 중 하나인 리스트에 대해 정리해보려고 한다.

 

리스트란?

리스트는 쉽게 말하면 기차처럼 요소와 요소가 연결되어 있는 것을 말한다.

이때 가장 처음에 있는 요소(노드)는 Head, 가장 마지막은 Tail 라고 부른다.

노드는 안에 data 와 다음 노드의 위치를 가지고 있는 포인터로 구성된다.

 

배열 vs 리스트 ?

리스트는 배열과 비슷하지만, 배열과 다르게 각 요소를 추가 / 삽입 / 삭제 할 때 유리하다는 장점이 있다.

배열의 경우에는 배열 선언 시 크기도 같이 선언해주어야 하지만, 리스트는 그럴 필요가 없다.

하지만, 배열과 다르게 리스트에서는 각 요소에 접근하는데 시간이 오래 걸리므로 

요소의 변경이 많은 경우 유리하게 사용할 수 있다.

 

리스트의 종류?

리스트의 종류는 크게 단순연결리스트, 이중연결리스트, 순환연결리스트로 나눌 수 있다.

 

단순연결리스트는 말 그대로 그냥 단순하게 한 방향으로 연결되어 있는 리스트를 의미한다.

 

 

위 그림에서 빨간색은 포인터 회색은 data 에 대한 정보를 가지고 있다.

단순연결리스트는 단방향으로 다음 노드에 대한 정보를 포인터에 담아서 저장되어 있는 형태이다.

 

 

이중연결리스트는 각 노드들이 서로 연결되어 있는 리스트를 의미한다.

 

위 그림에서 빨간색은 포인터 회색은 data 에 대한 정보를 가지고 있다.

이중연결리스트는 이전노드에 대한 정보도 저장하고 있다. 따라서 양방향으로 각 노드에 접근할 수 있는 형태이다.

 

 

순환연결리스트는 첫 Head 노드와 마지막 Tail 노드가 서로를 나타내도록 구성되어 순환가능한 연결리스트를 의미한다.

 

 

위 그림에서 추가된 점은 이중연결리스트 형태에서 헤드 노드의 이전 노드 포인터 정보에 Tail 노드의 위치가 저장되고

Tail 노드의 다음 노드 포인터 정보에는 Head 노드의 위치가 저장됨을 알 수 있다.

 

 

자바에서는?

자바에서는 컬렉션 프레임워크를 통해 다양한 자료구조를 제공한다.

 

그 중 List 인터페이스가 제공되는데 그 안에는 ArrayList 와 LinkedList 등을 제공함을 알 수 있다.

ArrayList는 동적배열 형태로 구현되어있고 LinkedList 는 이중연결리스트 형태로 구현되어 있다.

 

ArrayList 의 경우는 데이터를 순차적으로 수정하는 경우에 유리하고 LinkedList 는 중간 위치에 있는 데이터도 수정할 때 유리하게 사용할 수 있다.