JAVA 자료구조 (리스트) - 리스트란

리스트란 

생활 속의 리스트

리스트는 대표적인 자료구조 중 하나로 자료구조&알고리즘을 공부하다 보면 아주 흔하게 만나게 될 것이다. 리스트는 '줄 세워져 있는 데이터 ' 또는 '죽 늘어선 데이터'를 의미한다. 리스트의 예는 풍부하다. 정수 리스트, 어떤 그룹에 속하는 사람 리스트, 서비스를 기다리는 사람 리스트, 선물 받고 싶은 목록을 적은 위시 리스트, 위험한 사람들을 적은 블랙 리스트, 선물 보낼 사람들 리스트 등 끝없이 예를 들 수 있다.

 

리스트의 작업

리스트를 관리하기 위해 필요한 작업을 생각해보자. 우선, 리스트에 새 원소를 삽입할 일이 많을 것이다. 이때 1)원소를 리스트의 맨 뒤에 넣을지 맨 앞에 넣을지 중간 어디쯤 넣을지 알려줘야 할 것이다. 또한 2)리스트에서 원소를 삭제할 때는 어디에 있는 원소를 삭제할지 알려줘야 할 것이다. 3)특정 위치에 있는 원소가 아닌 특정 원소를 삭제해야 할 수도 있다. 이런식으로 어떤 자료구조에 필요한 작업들을 나열하면 그 자료구조를 대략 파악할 수 있다. 이전 게시물 <JAVA 자료구조 - 자료구조의 추상 데이터 타입> 에서 자료구조를 필요한 작업 목록으로 정의한 것을 추상 데이터 타입(ADT)으로 설명한 바 있다. 즉, ADT 리스트는 '리스트는 대락 이러이러한 작업으로 구성된 자료구조다'라고 정의한 것이다.

 

[그림 5-2]는 ADT 리스트로, 필요에 따라 이 작업 목록은 얼마든지 더하거나 뺄 수 있다.

그림 5-2 ADT 리스트

 

자바는 언어 자체에서 리스트를 기본 자료구조로 제공하지 않고 java.util 패키지에서 제공한다.

 

3. 리스트의 구현

리스트의 내부가 어떻게 구현되는지 정확하게 이해하는 일이 중요하다. 그래야 리스트를 적절하게 이용할 수 있고, 필요에 따라 소스를 수정하거나 확장할 수 있다. 혹은 목적에 맞게 리스트를 직접 만들어야 할 때도 있다.

 

리스트의 핵심을 파악하기에 충분한 정도의 집합을 선택하여 리스트를 구현해보자. 리스트를 구현하는 두 가지 대표적인 방법이 있다. 배열에 원소들을 쭉 배치하는 방법과 링크를 이용해 원소들을 연결하는 방법이다.

 

배열을 이용한 리스트는 시작 위치부터 빈자리 없이 자료를 순서대로 연속으로 저장하므로 논리적인 순서와 물리적인 순서가 일치하고 원소를 삽입하거나 삭제해도 빈자리가 없이 자료가 순서대로 연속하여 저장된다. 반면, 연결 리스트를 이용하면 물리적 위치나 순서와 상관없이 링크에 의해 논리적인 수선를 표현하므로 삽입·삭제 연산을 하여 논리적인 순서가 변경되어도 링크 변경되고 물리적 순서는 변경되지 않는다.

 

배열을 이용한 리스트 구현은 가장 단순한 구현 방법으로, 메모리의 연속된 공간에서 데이터를 관리한다. 이 방법은 이름과 크기만 정하면 되므로 편리하다. 반면 큰 단점이 있다. 리스트에 원소가 얼마나 들어올지 예상하기는 쉽지 않으므로 배열을 사용할 경우 충분한 공간을 확보해두고 작업을 시작해야 하기 때문에 대체로 공간 낭비가 심하다. 공간을 낭비하지 않으려면 배열의 크기를 빠듯하게 잡아놓아야 하는데 이 경우 다 차면 배열을 할당받아 원소를 모두 옮겨주는 작업을 자주 해야하므로 상당히 번거롭다. 그럼에도 불구하고 배열 방식은 단순하고 효율성이 높아 리스트를 구현하기 좋다.

 

연결 리스트Linked List는 배열 공간 낭비를 피할 수 있는 자료구조다. 원소가 추가될 때마다 공간을 할당받아 추가하는 적 할당 방식을 따른다.

 

그림 5-4 배열 리스트 와 연결 리스트에서의 삭제 작업 비교

 

 

 

 

[출처 - 쉽게 배우는 자료구조 with 자바,  저 문병로]
https://www.hanbit.co.kr/store/books/look.php?p_code=B7033044159

IT CookBook, 쉽게 배우는 자료구조 with 자바