자바의 정석8-2 ArrayList, LinkedList

ArrayList

- ArrayList는 기존의 Vector를 개선한 것으로 구현원리와 기능적으로 동일!

 

컬렉션프레임웍의 List, Set, Map중 List의 구조

 

- Vector는 ArrayList와 달리 자체적으로 동기화 처리가 되어 있음(Vector와 ArrayList의 차이는 동기화 유무)

- List인터페이스를 구현해서, 저장순서가 유지되고 중복을 허용한다.

- 데이터(객체)의 저장공간으로 배열을 사용한다. (배열기반)

- 이름에 List가 붙으면 리스트인터페이스를 구현한다는 의미 + 순서, 중복 허용

- ArrayList를 생성할 때, 저장할 요소의 개수를 고려해서 실제 저장할 개수보다 약간 여유 있는 크기로 하는 것이 좋다.(자동적으로 크기가 늘어나긴 하지만 처리시간이 많이 소요됨)

 

Vector클래스의 소스코드

- 클래스 안에 객체 배열(Object [ ]) 포함 -> 모든 종류의 객체 저장 가능

---

ArrayList의 메서드

 

1) ArrayList의 생성자

 

ArrayList( )	기본 생성자
ArrayList(Collection c)	매개변수로 Collection을 받으면 Collection에 저장되어있는 것을 ArrayList에 저장(Collection끼리 변환할 때 자주 사용)
ArrayList(int initialCapacity)	배열의 길이를 지정

 

2) ArrayList의 추가 메서드

 

boolean add(Object o)	ArrayList에 추가하는 메서드(매개변수에는 저장할 객체) -> 성공하면 true 반환, 실패하면 false 반환
void add(int index, Object element)	저장위치(index)를 지정해 줄 수 있음
boolean addAll (Collection c)	Collection이 가지고 있는 요소를 그대로 저장
boolean addAll(int index, Collection c)	저장위치(index)를 지정해 줄 수 있음

 

3) ArrayList의 삭제 메서드

 

boolean remove(Object o)	ArrayList에서 삭제
Object remove(int index)	특정위치에 있는 객체를 삭제
boolean removeAll(Collection c)	Collection을 지정해주면 Collection에 있는 객체들을 삭제
void clear( )	ArrayList에 있는 모든 객체를 삭제

 

4) ArrayList의 검색 메서드

 

int indexOf(Object o)	객체가 어느 위치(몇 번째)에 저장되어 있는 지 찾기, 못 찾으면 -1 반환
int lastIndexOf(Object o)	indextOf는 왼쪽에서부터 검색 lastIndexOf는 오른쪽에서부터 검색
boolean contains(Object o)	지정된 객체가 존재하는지 있으면 true, 없으면 false
Object get(int index)	특정위치에 있는 객체 반환(객체 읽기)
Object set(int index, Object element)	특정위치에 있는 객체 변경
List subList(int fromIndex, int toIndex)	from 부터 to 사이에 있는 객체들을 뽑아서 새로운 리스트를 만듦(읽기 전용)
Object[ ] to Array( )	ArrayList가 가지고 있는 객체 배열을 반환
Object[ ] to Array(Object[ ] a)
boolean isEmpty( )	ArrayList가 빈리스트인지 확인
void trimToSize( )	빈 공간 제거
int size( )	ArrayList에 저장된 객체의 개수 반환

 

---

예제 1)

 

public class Ex11_1 {
	public static void main(String[] args) {
		// 기본 길이(용량, capacity)가 10인 ArrayList를 생성
		ArrayList list1 = new ArrayList(10);

		//(숫자)는 부가설명 뜻함
		list1.add(5); //(1) list1.add(new Integer(5);와 동일
		list1.add(new Integer(4));
		list1.add(new Integer(2));
		list1.add(new Integer(0));
		list1.add(new Integer(1));
		list1.add(new Integer(3));
		
		ArrayList list2 = new ArrayList(list1.subList(1, 4)); // (2)1번쩨 ~ 3번째 객체로 list2 생성
		System.out.println("list1:" + list1);  // list1:[5, 4, 2, 0, 1, 3]
		System.out.println("list2:" + list2);  // list2:[4, 2, 0]

		Collections.sort(list1); // (3)list1과 lis2를 정렬한다.(기본 오름차순 정렬)
		Collections.sort(list2); 
		System.out.println("list1:" + list1);  // list1:[0, 1, 2, 3, 4, 5]
		System.out.println("list2:" + list2);  // list2:[0, 2, 4]

		// lisst1이 list2의 모든 요소를 포함하고 있는가? 
		System.out.println("list1.containsAll(list2): " + list1.containsAll(list2));
		// list1.containsAll(list2): true

		list2.add("B");   // 추가하게 되면 기존의 값들이 한 칸씩 밀리게 됨
		list2.add("C");   // 원래코드 list2.add(new String("C"));
		list2.add(3,"A"); // 원래 그냥 add이면 맨 뒤에 추가되지만, 여기서는 3번째 자리에 A를 추가(추가할 위치 지정)
		System.out.println("list1:" + list1); // list1:[0, 1, 2, 3, 4, 5]
		System.out.println("list2:" + list2); // list2:[0, 2, 4, A, B, C]
		
		list2.set(3,"AA"); // 3번째 인덱스에 있는 것을 AA로 변경(기존에 있는 것을 삭제하고 변경)
		System.out.println("list1:" + list1);  // list1:[0, 1, 2, 3, 4, 5]
		System.out.println("list2:" + list2);  // list2:[0, 2, 4, AA, B, C]
		
		list1.add(0,"1");  // ArrayList에 문자열 1 추가 (기존에 있던 숫자 1과는 다름)
		// indexOf( )는 지정된 객체의 위치(인덱스)를 알려준다.
		System.out.println("index=" + list1.indexOf(new String("1"))); // 문자열 1의 위치(인덱스),index=0
		System.out.println("index=" + list1.indexOf(1));  // 숫자 1의 위치(인덱스),index=2
		System.out.println("list1:" + list1); // list1:[1, 0, 1, 2, 3, 4, 5]
		System.out.println("list2:" + list2); // list2:[0, 2, 4, AA, B, C]

		list1.remove(1); // 인덱스1번에 위치한 객체 삭제 
		System.out.println("list1:" + list1); // list1:[1, 1, 2, 3, 4, 5]
		list1.remove(new Integer(1)); // 숫자 1을 삭제
		System.out.println("list1:" + list1); // list1:[1, 2, 3, 4, 5]
		System.out.println("list2:" + list2); // list2:[0, 2, 4, AA, B, C]

		//list1에서 list2와 겹치는 부분만 남기고 나머지는 삭제한다
		System.out.println("list1.retainAll(list2): " + list1.retainAll(list2)); // list1.retainAll(list2): true
		System.out.println("list1:" + list1);  // list1:[2, 4]
		System.out.println("list2:" + list2);  // list2:[0, 2, 4, AA, B, C]
		
		//(4)list2에서 list1에 포함된 객체들을 삭제한다.
		for(int i=list2.size()-1;i>=0;i--) {  // ArrayList 배열명.size( )-> ArrayList의 크기
			if(list1.contains(list2.get(i)))  
				list2.remove(i);
		}
		System.out.println("list1:" + list1);  // list1:[2, 4]
		System.out.println("list2:" + list2);  // list2:[0, AA, B, C]
	}
}

 

(1) ArrayList에는 객체만 저장 가능하다 왜? Object[ ](객체배열)이기 때문에 list.add(5) 이 코드는 autoboxing에 의해 기본형 -> 참조형으로 자동 변환된 것이다. 실제 코드는 list.add(new Integer(5))이다.

 

(2) subList의 내용을 바꾸지 않고 읽기만 한다면 ArrayList의 객체 생성을 안 해도 되지만 subList와 같은 내용의 ArrayList를 만들고 싶다면 새로운 new ArrayList를 선언해야 함

// List sub = list1.subList(1,4); sub은 읽기만 가능 [4, 2, 0]

// ArrayList list2 = new ArrayList(sub) sub와 같은 내용의 ArrayList 생성  

 

(3) ArrayList(Collection c); 코드에서 Collection은 인터페이스이고 Collections.sort(list1); 코드에서 Collections는 유틸 클래스

 

(4)

1. get(i)로 list2에서 하나씩 꺼낸다. 2. contains( )로 꺼낸 객체가 list1에 있는지 확인 3. remove(i)로 해당 객체를 list2에서 삭제

-> list2.size( )는 6이 되면 Index 6 out of bounds for length 6라는라는 오류가 뜸(list size는 0부터 시작!) 배열은 index[5]부터 시작해서 -1을 해준다.

-> for문의 변수를 list 2.size( )-1부터 감소시키면서 거꾸로 반복시킨 이유: 만약 변수 i를 증가시켜가면서 삭제하면, 한 요소가 삭제될 때마다 빈 공간을 채우기 위해 나머지 요소들이 자리이동을 하기 때문에 올바른 결과를 얻을 수 없다. (자세한 건 뒤에)

-> 제어변수를 감소시켜가면서 삭제를 해야(뒤에서부터 삭제를 해야) 자리이동이 발생해도 영향을 받지 않고 작업이 가능하다.

 

---

ArrayList에 저장된 객체의 삭제 과정

 

 

 

- list.size( )는 5 / remove(0), remove(1), remove(2) … 이렇게 삭제됨

- 앞에서부터 삭제되기 때문에 시간도 더 걸릴 뿐 아니라 올바르지 못한 결과가 나올 수 있음

 

 

- list.size( )-1은 4 / remove(4), remove(3), remove(2) … 이렇게 삭제됨

- 빠르고 정확함

- 삭제했는데도 숫자가 남아 있다면 끝에서부터 지우지 않았기 때문!

 

---

LinkedList

배열의 장단점

 

장점	구조가 간단하고 데이터를 읽는 데 걸리는 시간(접근시간,access time)이 짧다
	index[0]을 읽어오는 것과 index[5]을 읽어오는 시간 동일
단점	- 크기를 변경할 수 없다.(프로그램 실행 중에) 1) 더 큰 배열 생성 2) 기존 내용을 복사 3) 참조변경 - 크기를 변경해야 하는 경우 새로운 배열을 생성 후 데이터를 복사해야 함 - 크기 변경을 피하기 위해 충분히 큰 배열을 생성하면, 메모리가 낭비됨
	- 비순차적인 데이터의 추가, 삭제에 시간이 많이 걸린다. (비순차적-> 중간에 객체를 추가, 삭제, 변경하는 것) - 데이터를 추가하거나 삭제하기 위해, 다른 데이터를 옮겨야 함 - 하지만 순차적인 데이터 추가(끝에 추가)와 삭제(끝부터 삭제)는 빠르다

 

---

LinkedList – 배열의 단점을 보완

- 배열과 달리 LinkedList는 불연속적으로 존재하는 데이터를 연결(link)(배열은 각 요소가 연속적)

 

1) 데이터의 삭제: 단 한 번의 참조 변경만으로 가능

 

 

- 삭제하고자 하는 요소의 이전요소가 삭제하고자 하는 요소의 다음 요소를 참조하도록 변경

- 배열처럼 데이터를 이동하기 위해 복사하는 과정이 없어서 처리속도가 매우 빠름

 

LinkedList의 구조

 

Node -> 참조변수와 데이터를 갖고있는 이 네모 박스

next -> 다음 노드(자신의 다음 노드가 무엇인지 알려주는 참조변수)

Object obj -> 데이터

- 주소가 0x200인 노드가 다음 요소(노드)의 주소인 0x300(next)을 저장, 가리키고 있고, 데이터는 0(data)이다.

 

 

2) 데이터의 추가: 한 번의 Node객체 생성과 두 번의 참조 변경만으로 가능

 

 

- 새로운 요소를 생성한 다음 추가하고자 하는 위치의 이전 요소의 참조를 새로운 요소에 대한 참조로 변경해주고, 새로운 요소가 그다음 요소를 참조하도록 변경함

---

링크드 리스트(Linked list) – 연결리스트. 데이터 접근성이 나쁨

 

 

- 불연속적이라서 한 번에 다음 요소로 갈 수 없음 예) index[0]에서 바로 index[3]으로 갈 수 없음

- 링크드 리스트는 이동 방향이 단방향이기 때문에 다음 요소에 대한 접근은 쉽지만 이전 요소에 대한 접근은 어렵다.

---

더블리 링크드 리스트(doubly linked list) – 이중 연결리스트, 접근성 향상

 

 

- 서로 근접한 두 요소를 앞뒤로 이동할 수 있게 연결함(기존의 LinkedList는 index[1] -> index[0]으로 갈 수 없음, 자기 다음 요소밖에 모름)

- LinkedList에 참조변수를 하나 더 추가해 다음 요소에 대한 참조 뿐 아니라 이전 요소에 대한 참조가 가능

 

doubly linked list의 구조

 

- next -> 다음 노드

- previous -> 이전의 노드

- obj -> 데이터

---

더블리 써큘러 링크드 리스트(doubly circular linked list) – 이중 원형 연결리스트

 

 

- doubly linked list의 첫 번째 요소와 마지막 요소를 서로 연결시킨 것(double linked list의 접근성을 보다 향상함)

- 이렇게 하면 마지막 요소의 다음 요소가 첫 번째 요소가 되고, 첫 번째 요소의 이전 요소가 마지막 요소가 된다.

-> LinkedList클래스는 ‘doubly linked list’로 구현되어 있음

 

---

ArrayList(배열기반) vs LinkedList(연결기반) – 성능 비교

 

array의 구조와 linkedlist의 구조

-> 배열기반(ArrayList)은 연속적, 연결기반(LinkedList)은 불연속적

-> 배열의 경우 인덱스가 n인 요소의 값을 얻어 오고자 한다면 수식을 계산하면 해결됨

    인덱스가 n인 데이터의 주소 = 배열의 주소 + n * 데이터 타입의 크기

예) arr[2]에 저장된 값을 얻어 오기 n은 2, 모든 참조형 변수의 크기는 4byte, 생성된 배열의 주소는 0x100 -> index[2]인 요소가 저장되어 있는 주소는 0x100 + 2 * 4 = 0x108이 된다.

 

컬렉션	읽기(접근시간)	추가/삭제	비고
ArrayList	빠르다	느리다	순차적인 추가삭제는 더 빠름. 비효율적인 메모리의 사용(성능을 높이기 위해 배열을 크게)
LinkedList	느리다	빠르다	데이터가 많을수록 접근성이 떨어짐