[Collection Framework] ArrayList, LinkedList

Collection은 다수의 데이터를 쉽게 처리 하도록 표준화된 방법을 제공하는 클래스들을 지칭한다.

 

		Collection인터페이스			Map
	↗		↖
List인터페이스				Set인터페이스

List와 Set인터페이스를 공통부분을 추출해서 Collection인터페이스를 정의하였다. Map은 다른 두 인터페이스와 달리 두 가지의 데이터를 다루기 때문에 같은 계층에 포함되지 못하였다.

 

 

컬렉션 클래스
List	- 저장 순서를 유지하고, 데이터 중복 허용
	종류 : ArrayList, LinkedList, stack
Set	- 저장 순서를 유지하지 않고, 중복도 허용하지 않음.
	종류 : HashSet, TreeSet
Map	- (키, 값)의 형태로 저장되어 저장 순서를 유지하지 않고 값만 중복 허용
	종류 : HashMap, TreeMap, HashTable 등

 

 

 

 

▶ 기존 클래스인 Vector클래스(List계열)와 HashTable(Map계열)

멀티쓰레드 프로그래밍에서는 하나의 객체를 여러 쓰레드가 동시 접근을 할 우려가 있기 때문에 그것을 막는 동기화라는 기술이 필요하다.

Vector클래스와 HashTable클래스는 컬렉션 프레임워크가 만들어지기 이전부터 존재하는 클래스로써 자체적으로 동기화 처리가 되어있다. 하지만 모든 환경이 멀티쓰레드 프로그램 환경이 아니기 때문에 이 경우 Vector와 HashTable의 사용은 성능 저하의 원인이 될 수가 있다.

ArrayList나 HashMap같은 클래스는 동기화 처리가 되지 않았기 때문에 가급적이면 위에 언급한 두 클래스의 사용을 지양하고 이 두 가지 클래스를 사용하는 것이 바람직하다.

그렇다고 ArrayList나 HashMap클래스가 동기화가 되지 않는 것은 아니다.

java.util.Collections 객체를 보면 컬렉션 프레임워크 클래스에 대한 동기화 메서드를 제공하기 때문에, 동기화가 필요할 경우 사용하면 된다.

 

 

 

 

 

▶ ArrayList

ArrayList는

- 데이터의 저장순서를 유지하고, 중복을 허용한다.

- ArrayList는 Object타입의 배열을 이용해서 데이터를 순차적으로 저장한다.

 

ArrayList는 인스턴스를 생성하고, 데이터를 저장 하다가 더이상 저장할 데이터 공간이 없을때 저장 공간이 더 큰 새로운 배열을 생성하여, 기존에 있는 배열데이터를 새로 생성한 배열데이터에 복사하는 작업을 한다.

 

그래서 ArrayList같은 배열을 기반으로하는 자료구조를 사용할 때는 성능을 고려한다면 객체의 인스턴스를 생성할 때 생성자 파라미터를 통해 되도록 배열 복사가 일어나는 것을 방지하기 위해 배열의 길이를 지정해주는 것이 좋다.

ArrayList는 remove() 메서드를 쓸 때에 삭제할 데이터가 마지막 index에 위치한 데이터가 아니면 배열의 데이터가 위치이동을 하기 때문에 유념하고 프로그래밍 하여야한다.

 

Colored By Color Scripter™

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

import java.util.*;   public class ListEx1 {     public static void main(String[] args){                  List list = new ArrayList(4);                  list.add(1);         list.add(2);         list.add(3);         list.add(4);                  for(int i=0; i<list.size(); i++){             list.remove(i);         }                  System.out.println(list);         //결과는 [2,4]가 콘솔창에 찍힌다. 순서대로 삭제하면 삭제 되지않는다.              } } }

 

위에서 보면 ArrayList의 remove()메서드 사용시 앞부터 순차 삭제를 하게 되면 데이터는 지워지지 않고 남는다. 이유는 삭제하려는 index가 리스트의 마지막 위치가 아니면 데이터의 위치이동이 일어나기 때문이다.

그래서 ArrayList의 마지막 위치부터 삭제작업을 하거나 이 특징을 유념하고 작업하여야 한다.

 

 

 

 

 

▶ LinkedList

배열 형태로 데이터를 저장하는 ArrayList는 차례대로 데이터를 저장하고, 마지막 위치부터 데이터를 저장하는 능력은 빠르지만 배열의 데이터를 중간에 추가하는 경우 등에는 데이터가 들어갈 빈자리를 만들기 위해서 데이터를 복사해서 이동해야 하는 불편함이 있다. 성능면도 좋지 못하다. 이러한 배열 형태의 자료를 보완하기 위해서 링크드 리스트가 만들어졌다.

 

LinkedList는

- 배열처럼 순차적인 구조로 되어있지 않고, 데이터들을 주소값을 이용하여 각 요소들을 연결한 형태로 되어있다.

- 각 요소들은 다음요소의 주소값과 자신의 값을 가지고 있다.

 

링크드 리스트에서 데이터의 추가 삭제작업은 간단하다. 추가 시에는 이전 요소가 추가될 요소를 참조하면 되고, 다음 요소는 추가될 요소가 참조하면 된다. 삭제시에는 단순히 삭제할 요소의 이전 요소가 삭제할 요소의 다음 요소를 참조 하기만 하면된다. 이렇듯 간단하기 때문에 데이터의 추가 삭제 작업이 빠르다.

 

링크드리스트는 단방향의 접근만 가능하기 때문에 이전 요소에 대한 접근이 어렵다. 이 때문에 만들어진 것이 더블링크드 리스트다.

더블링크드 리스트는 단순히 다음요소의 주소값과 자신의 값을 가진 링크드 리스트에 이전요소의 주소값 참조변수를 추가시킨 형태이다.

 

 

 

 

이처럼 ArrayList와 LinkedList를 비교해 보자면

ArrayList의 경우 순차적인 데이터의 추가, 삭제(삭제의 경우 배열 생성 작업을 하지 않는 마지막인덱스 부터 삭제)가 빠르다.

LinkedList의 경우 임의의(중간) 인덱스에 대한 데이터의 추가 삭제작업이 빠르다.