[Java] Collection - (2) List란?

List는 대표적인 선형 자료구조로 각 요소가 삽입되는 위치를 정밀하게 제어할 수 있다는 특징이 있습니다. 사용자는 목록의 위치를 기준으로 요소에 접근하고 목록에서 요소를 검색할 수 있습니다. 배열과 비슷하지만 배열은 공간이 고정적이지만 List는 요소의 갯수에 따라 동적으로 크기를 변화시켜 사용할 수 있습니다.

List는 일반적으로 중복 요소를 허용합니다. 좀 더 구체적으로, List는 일반적으로 a.equals(b)와 같은 a과 b 요소의 쌍을 허용하며, 일반적으로 null조차 중복으로 여러 null 요소를 저장할 수 있도록합니다. 또, List의 요소에 대한 추가, 제거, 동등 및 해시코드 메서드를 지원합니다. List를 상속한 대표적은 클래스는 ArrayList, LinkedList, Vector, Stack이 있습니다.

List 인터페이스의 Method

ArrayList

ArrayList는 List 인터페이스를 상속받은 클래스로 크기가 가변적으로 변하는 선형리스트입니다. 일반적인 배열과 같은 순차리스트이며 인덱스로 내부의 객체를 관리한다는점등이 유사하지만 한번 생성되면 크기가 변하지 않는 배열과는 달리 ArrayList는 객체들이 추가되어 저장 용량(capacity)을 초과한다면 자동으로 부족한 크기만큼 저장 용량(capacity)이 늘어난다는 특징을 가지고 있습니다. Generic 선언으로 ArrayList의 자료형이 결정되기 때문에 Primitive 타입은 사용할 수 없고 Reference 타입만 선언할 수 있습니다.

ArrayList에 값을 추가하려면 ArrayList의 add(index, value) 메소드를 사용하면 됩니다. index를 생략하면 ArrayList 맨 뒤에 데이터가 추가되며 index중간에 값을 추가하면 해당 인덱스부터 마지막 인덱스까지 모두 1씩 뒤로 밀려납니다. 왜냐하면 ArrayLIst는 데이터를 Object[] 형태로 관리하기 때문에 직접 옮겨주는 로직을 실행하게 됩니다. 이 경우 데이터가 많은 경우 성능에 안좋은 영향을 미치기 때문에 중간에 데이터를 insert 해야할 경우가 많다면 LinkedList를 활용하는 것도 좋은 방법입니다. 

 

LinkedList

연결 리스트(LinkedList)는 각 노드(Node)가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식의 자료구조입니다. 데이터를 담고 있는 노드들이 연결되어 있고, 노드의 포인터가 이전 노드와 다음 노드와의 연결을 담당합니다. Node는 LinkedList에 객체를 추가하거나 삭제하면 앞뒤 링크만 변경되고 나머지 링크는 변경되지 않습니다. 중간에 데이터를 추가나 삭제하더라도 전체의 인덱스가 한 칸씩 뒤로 밀리거나 당겨지는 일이 없기에 ArrayList에 비해서 데이터의 추가나 삭제가 용이하나, 인덱스가 없기에 특정 요소에 접근하기 위해서는 순차 탐색이 필요로 하여 탐색 속도가 떨어진다는 단점이 있습니다. 그러므로 탐색 또는 정렬을 자주 하는 경우엔 배열을 사용하고 데이터의 추가/삭제가 많은 경우 연결 리스트를 사용하는 것이 좋습니다.

ArrayList는 내부 배열에 객체를 저장해서 인덱스로 관리하는데 비해서 LinkedList는 위와 같이 인접 참조를 링크해서 체인처럼 관리합니다.

 

Vector

Vector는 ArrayList와 동일한 내부구조를 가지고 있습니다. ArrayList와 마찬가지로 Vector 내부에 값이 추가되면 자동으로 크기가 조절되며 그다음 객체들은 한 자리씩 뒤로 이동됩니다. 하지만 Vector와 Arraylist의 한가지 다른 점이 있는데 Vector는 동기화된 메소드로 구성되어 있기 때문에 멀티 스레드가 동시에 이 메소드들을 실행할 수 없고, 하나의 스레드가 실행을 완료해야만 다른 스레드들이 실행할 수 있습니다. 그래서 멀티 스레드 환경에서 안전하게 객체를 추가하고 삭제할 수 있습니다.

벡터는 항상 동기화되는 장점이자 단점을 가지고 있습니다. 스레드가 1개일때도 동기화를 하기 때문에 ArrayList보다 성능이 떨어집니다. Arraylist는 기본적인 기능은 벡터와 동일하나 자동 동기화 기능이 빠져있고, 동기화 옵션이 존재합니다. 그리고 벡터에 비해 속도가 더 빠르기 때문에 벡터에 비해 많이 쓰이고 있습니다.

 

Stack

자료 구조 중 하나인 Stack의 사전적 정의는 '쌓다', '더미'입니다. 상자에 물건을 쌓아 올리듯이 데이터를 쌓는 자료 구조라고 할 수 있습니다. Stack의 가장 큰 특징은 나중에 들어간 것이 먼저 나오는 (Last In First Out)의 형태를 띈다는 것입니다. 이 방식을 가진 자료구조인 Stack을 활용하여 다양한 문제를 해결할 수 있습니다. 자바에서 Stack은 java.util.Stack을 import하면 바로 사용할 수 있습니다.

Stack의 경우 Vector클래스를 상속받고 있고, java에서 지원하는 Stack 클래스의 메소드들도 모두 Vector에 있는 메소드를 이용하여 구현 되고 있습니다.

 

---

참고자료

• 코딩팩토리's blog
• st-lab's blog