자바의 강력한 도구인 Collection에 대해 배우는 시간입니다. 구조와 원리에 대해서는 “Java로 배우는 자료구조” 코스에서 좀 더 깊게 이해를 하실 수 있습니다. 이 강의에서는 이러한 도구들이 있고 어떤 특징이 있는지, 어떻게 사용하는지에 대해서만 알아봅니다.

ㅤ

목차

1. Collection

2. List<E>

3. ArrayList<E>

4. LinkedList<E>

ㅤ

1. Collection

프로그래밍을 하다 보면 가장 많이 겪게 되는 문제가 데이터와 관련된 문제입니다. 데이터를 어디에 저장할 것인지, 데이터를 어떻게 저장하고 꺼낼 것인지, 관리할 것인지에 대한 부분을 고민하게 됩니다.

우리는 실전 프로그래밍 2 “메모장”을 지나오며 프로그램이 실행되면 메모를 저장할 수 있는 배열의 크기를 유동적으로 변경할 수 없는 문제가 있었습니다. 많은 메모를 작성하기 위해 배열의 크기를 크게 늘릴 수 있으나 그렇게 되면 프로그램을 실행할 때 필요 없는 메모리 공간까지 할당받아 사용하는 비효율적인 상황을 만들 수 있습니다.

ㅤ

실전 프로그래밍 2 메모장 코드

NoteEntity[] noteEntities = new NoteEntity[100000];
// 모든 메모리 공간을 사용하지는 않는다

현실 세계의 자원의 유한함은 컴퓨터의 세계에서도 동일하게 존재합니다. 그러므로 한정된 메모리 공간에서 프로그램이 문제없이 잘 돌아가도록 하는 것이 굉장히 중요합니다.

한정된 메모리 공간에서 데이터를 어떻게 잘 관리하고 저장하고 꺼낼 수 있는지에 대한 문제를 해결하기 위해, Collection이라는 자료구조 라이브러리가 만들어졌습니다.

자료구조란 컴퓨터 과학에서 효율적인 접근 및 수정을 가능케 하는 자료의 조직, 관리, 저장을 의미합니다.

Collection은 자료구조를 도와주는 도구이며 Collection Interface를 구현한 구현체는 java.util package에 포함되어 있습니다. 해당 도구들의 기본적인 컨셉은 어떻게 데이터를 저장하고 가져오는지에 초점이 맞춰져있고 여러 가지가 구현되어 있는데 도구에 따라 사용 용도도 다르고 성능도 다릅니다.

그럼 본격적으로 Collection 도구에 대해서 알아보겠습니다.

ㅤ

2. List<E>

순서가 있는 자료구조로 만들어진 경우는 List Interface를 구현합니다.

그리고 List Interface를 구현한 클래스들은 ArrayList, LinkedList, Vector, Stack등이 존재합니다.

ㅤ

3. ArrayList<E>

ArrayList는 가변 배열이라고 볼 수 있습니다. 내부 구현체는 배열을 이용하여 만들어졌으며, 원리는 다음과 같습니다.

ArrayList 인스턴스가 생성되면 기본값(최초 10) 또는 사이즈(직접 지정가능)에 맞게 배열을 생성합니다. 그리고 배열이 꽉차게 되면 새로운 배열을 만들어서 기존의 값을 Copy 하는 단순한 방식으로 이루어져 있습니다.

만약에 ArrayList의 데이터가 삭제될 경우 다음과 같은 작업이 발생합니다.

data3이 삭제되면 2번 index에 저장된 값이 비어있게 되므로 2번 index 이후의 데이터를 앞으로 당겨야 됩니다. 데이터를 당기는 방법은 3번 index에 저장된 값부터 7번 index에 저장된 값을 Copy 후 2번 index 부터 덮어씁니다. 그리고 7번 index에 null 값을 저장합니다.

Copy 하여 저장하는 방식은 java code가 아닌 native code로 실행됩니다.

ㅤ

최초 생성시 물리 적인 배열 크기의 기본값(크기 미지정시)

10

ㅤ

장점

• 배열로 만들어졌기 때문에 인덱스를 통해서 특정 데이터에 빠르게 접근할 수 있습니다.

ㅤ

단점

• 생성된 배열의 공간이 꽉 찰 때마다 새로운 배열을 생성하고 Copy 하는 방식을 택하므로 그 과정에서 지연이 발생합니다.

• 배열의 데이터를 삭제 시 Copy 하는 방식을 택하므로 그 과정에서 지연이 발생합니다.

• 데이터가 많아질수록 Copy에 따른 지연시간이 늘어납니다.

ㅤ

사용용도

• 데이터의 양이 일관적이고 삽입, 삭제가 빈번하지 않은 경우에 사용한다.

• 데이터의 접근 속도가 중요할 때 사용한다.

ㅤ

ArrayList의 생성

import java.util.ArrayList;

ArrayList<String> texts = new ArrayList<>();

// 최초 공간 30으로 지정
ArrayList<String> texts = new ArrayList<>(30);

ㅤ

ArrayList의 데이터 삽입

import java.util.ArrayList;

ArrayList<String> texts = new ArrayList<>();

texts.add("딸기");
texts.add("포도");
texts.add("사과");

ㅤ

ArrayList에 저장된 논리적인 공간의 크기

import java.util.ArrayList;

ArrayList<String> texts = new ArrayList<>();

texts.add("딸기");
texts.add("포도");
texts.add("사과");

int size = texts.size();
// 크기 3

ㅤ

ArrayList의 특정 index에 데이터를 삽입하기

import java.util.ArrayList;

ArrayList<String> texts = new ArrayList<>();

texts.add("딸기");
texts.add("포도");
texts.add("사과");

…

// set(index, 값);
texts.set(1, "포도");

set(index,value) 메서드의 주의할 점은, 배열로 생성된 물리적인 공간의 크기는 10이라고 하더라도 논리적인 공간(size)은 3이기 때문에 인덱스 값이 논리적인 공간을 넘어 접근할 수 없습니다.

논리적인 공간을 넘어 접근할 경우 IndexOutOfBoundsException이 발생합니다.

ㅤ

ArrayList의 특정값에 접근

import java.util.ArrayList;

ArrayList<String> texts = new ArrayList<>();

// index 0
texts.add("딸기");
// index 1
texts.add("포도");
// index 2
texts.add("사과");

…

// get(index);
String text = texts.get(1);
// 포도

get(index) 메서드의 주의할 점은, 배열로 생성된 물리적인 공간의 크기는 10이라고 하더라도 논리적인 공간(size)은 3이기 때문에 인덱스 값이 논리적인 공간을 넘어 접근할 수 없습니다.

논리적인 공간을 넘어 접근할 경우 IndexOutOfBoundsException이 발생합니다.

그리고 배열처럼 인덱스는 0부터 시작합니다.

ㅤ

ArrayList의 값 삭제

import java.util.ArrayList;

ArrayList<String> texts = new ArrayList<>();

// index 0
texts.add("딸기");
// index 1
texts.add("포도");
// index 2
texts.add("사과");

…

// 인덱스를 이용한 값 삭제
texts.remove(1);

// 값을 검색하여 값 삭제
texts.remove("포도");

ArrayList는 배열 기반이므로 remove(index) 메서드를 이용한 삭제는 굉장히 빠르나, remove(value) 메서드를 통해 저장된 값을 찾아 삭제하는 방식은 index 0번 부터 순차적으로 찾아 삭제하기 때문에 효율이 좋지 않습니다.

ㅤ

ArrayList의 논리적인 공간을 늘리기

import java.util.ArrayList;

ArrayList<String> texts = new ArrayList<>();

for (int i = 0; i < 20; i++) {
    // null 값으로 채운다
    texts.add(null);
}

int size = texts.size();
// 20

만약에 논리적인 공간을 늘리고 싶으면 null 값을 채워 넣어 늘릴 수 있습니다.

ㅤ

List 인터페이스를 구현하는 ArrayList

import java.util.List;
import java.util.ArrayList;

List<String> texts = new ArrayList<>();

다형성의 특징으로 ArrayList의 참조값을 List 참조 자료형에 저장할 수 있습니다.

다만 List의 공통적인 인터페이스만 선언되어있기 때문에 ArrayList의 모든 메서드를 사용할 수는 없습니다.

ㅤ

메모장의 NoteEntity[] noteEntities를 ArrayList로 바꿔봅시다.

import java.util.List;
import java.util.ArrayList;

List<NoteEntity> noteEntities = new ArrayList<>();

ArrayList를 실전 프로그래밍 2 메모장 프로젝트에서 변경해서 코드를 작성해봅시다. 코드 변경이 많이 발생하지만 변경해서 적용하는 것도 큰 의미가 있습니다.

ㅤ

4. LinkedList<E>

LinkedList는 Node에 의해 데이터들이 연결되어 있는 리스트입니다. 그래서 연결 리스트라고도 불립니다. LinkedList를 이해하기 위해서는 Node라는 컨셉을 이해해야 하는데요.

LinkedList는 데이터를 배열에 저장하는 구조가 아니며 Node라는 객체에 data를 저장합니다. 그리고 Node는 Node끼리 참조 값을 가지고 있는 이중 연결 리스트로 구성되어 있습니다.

익숙하지 않거나 처음 보는 경우는 정말 이해가 안 되실 겁니다. 그렇다고 좌절하지 않으셔도 됩니다. 컴퓨터 공학과 애들도 자료구조 시간에 겪는 장벽 중 하나입니다.

Node next 변수에는 다음 Node의 인스턴스 참조 값을 저장하고 있습니다.

좌측의 Node를 현재 Node라고 하면 우측의 Node를 다음 Node라고 할 수 있습니다.

현재 Node에서는 Node next 변수에 다음 Node의 참조 값만 저장하고 있기 때문에 다음 Node만 접근할 수 있습니다.

Node1에서는 Node2에는 접근할 수 있지만 Node3에는 접근할 수 없습니다. Node2에서만 Node3에 접근할 수 있습니다.

data2를 삭제시에는 Node1에서는 Node3의 참조값을 저장하고 Node3에서는 Node1의 참조값을 저장합니다.

LinkedList에서는 Node에서 참조값을 삭제하는 방식으로 데이터를 삭제합니다. 그러므로 ArrayList 보다 삭제시 지연시간이 짧습니다. 그리고 LinkedList에 저장된 데이터가 많다 하더라도 데이터 삭제시간은 동일합니다. 그와 반대로 ArrayList는 저장된 데이터의 양에 따라 삭제시간 지연이 늘어납니다.

ㅤ

장점

• 데이터의 삽입이나, 삭제 연산이 빠르다.

ㅤ

단점

• 특정 데이터를 찾으려면 최초 생성 Node부터 차례로 Node를 검색해야 하기 때문에 데이터 접근 속도가 ArrayList 같은 index 방식보다 느리다.

• LinkedList에 저장된 데이터가 100,000개라면 99,999 번째 데이터에 접근하려면 Node를 99,999번 이동해야 한다.

ㅤ

사용용도

• 데이터에 접근하는 빈도보다 삽입, 삭제가 많을 경우에 사용한다.

• (다만 데이터가 많을수록 삭제할 Node 찾는 검색 시간은 오래 걸림)

• 맨 앞의 데이터 삭제나, 맨 뒤의 데이터 삭제가 빈번할 때 사용한다.

ㅤ

LinkedList의 생성

import java.util.LinkedList;

LinkedList<String> texts = new LinkedList<>();

ㅤ

LinkedList의 데이터 삽입

import java.util.LinkedList;

LinkedList<String> texts = new LinkedList<>();

texts.add("딸기");
texts.add("포도");
texts.add("사과");

// 딸기 -> 포도 -> 사과

// 첫 번째 Node의 앞에 삽입
texts.addFirst("시작");

// 시작 -> 딸기 -> 포도 -> 사과

// 마지막 Node의 뒤에 삽입
texts.addLast("마지막");

// 시작 -> 딸기 -> 포도 -> 사과 -> 마지막

ㅤ

LinkedList에 저장된 논리적인 공간의 크기

import java.util.LinkedList;

LinkedList<String> texts = new LinkedList<>();

texts.add("딸기");
texts.add("포도");
texts.add("사과");

int size = texts.size();
// 크기 3

ㅤ

LinkedList의 특정 index에 데이터를 삽입하기

import java.util.LinkedList;

LinkedList<String> texts = new LinkedList<>();

texts.add("딸기");
texts.add("포도");
texts.add("사과");

…

// set(index, 값);
texts.set(1, "귤");


// 딸기 -> 귤 -> 사과

set(index, value) 메서드의 주의할 점은, 논리적인 공간(size)은 3이기 때문에 인덱스 값이 논리적인 공간을 넘어 접근할 수 없습니다.

논리적인 공간을 넘어 접근할 경우 IndexOutOfBoundsException이 발생합니다.

ㅤ

LinkedList의 특정 index에 사이에 데이터를 삽입하기

import java.util.LinkedList;

LinkedList<String> texts = new LinkedList<>();

texts.add("딸기");
texts.add("포도");
texts.add("사과");

…

// add(index, 값);
texts.add(1, "중간!");

// 딸기 -> 중간! -> 포도 -> 사과

add(index, value) 메서드는 Node와 Node 사이에 삽입하는 방식입니다.

add(index, value) 메서드의 주의할 점은, 논리적인 공간(size)은 3이기 때문에 인덱스 값이 논리적인 공간을 넘어 접근할 수 없습니다.

논리적인 공간을 넘어 접근할 경우 IndexOutOfBoundsException이 발생합니다.

ㅤ

LinkedList의 특정값에 접근

import java.util.LinkedList;

LinkedList<String> texts = new LinkedList<>();

// index 0
texts.add("딸기");
// index 1
texts.add("포도");
// index 2
texts.add("사과");

…

// get(index);
String text = texts.get(1);
// 포도

get(index) 메서드의 주의할 점은, 논리적인 공간(size)은 3이기 때문에 인덱스 값이 논리적인 공간을 넘어 접근할 수 없습니다. (set(value), add(index, value) 메서드와 동일)

논리적인 공간을 넘어 접근할 경우 IndexOutOfBoundsException이 발생합니다.

그리고 인덱스는 0부터 시작합니다.

ㅤ

LinkedList의 값 삭제

import java.util.LinkedList;

LinkedList<String> texts = new LinkedList<>();

// index 0
texts.add("1");
// index 1
texts.add("2");
// index 2
texts.add("3");
// index 3
texts.add("4");
…

// 인덱스를 이용한 값 삭제
texts.remove(1);

// 값을 검색하여 값 삭제
texts.remove("코드라떼");

// 맨 앞의 값을 삭제
texts.removeFirst();

// 맨 뒤의 값을 삭제
texts.removeLast();

LinkedList의 remove(index) 메서드는 맨 앞 또는 맨 뒤의 Node 중 접근하기 가장 가까운 Node 에서 시작하여 찾아 삭제하며, remove(value) 메서드는 index 0번 부터 순차적으로 찾아 삭제합니다.

removeFirst()는 맨 앞의 노드를 삭제하므로 굉장히 빠릅니다.

removeLast()는 맨 뒤의 노드를 삭제하므로 굉장히 빠릅니다.

ㅤ

List 인터페이스를 구현하는 LinkedList

import java.util.List;
import java.util.LinkedList;

List<String> texts = new LinkedList<>();

다형성의 특징으로 LinkedList의 참조값을 List 참조 자료형에 저장할 수 있습니다. 다만 List의 공통적인 인터페이스만 선언되어있기 때문에 LinkedList의 모든 메서드를 사용할 수는 없습니다.

ㅤ

메모장의 NoteEntity[] noteEntities를 LinkedList로 바꿔봅시다.

import java.util.List;
import java.util.LinkedList;

List<NoteEntity> noteEntities = new LinkedList<>();

LinkedList를 실전 프로그래밍 2 "메모장" 프로젝트에서 변경해서 코드를 작성해봅시다.

ArrayList와 마찬가지로 메모리 공간이 허락하는 한 데이터를 계속해서 저장할 수 있습니다.