자료 구조
대학교 수업 때 자료 구조가 있었던 것이 생각난다.
지금 보면 '자료 구조가 뭘 말하길래 자료 구조라는 이름이 붙었을까?' 라는 궁금증이 생기는데
그 때는 관심도 없었던 걸 보면 나에게도 참 많은 변화가 일어나고 있는 것 같다. (ㅠㅠㅋㅋ)
자료 구조란, 여러 데이터를 구조화 해서 다루는 것이다.
말 그대로 데이터(자료)를 구조화(구조)한다는 이야기.
자바에서는 다양한 자료 구조를 지원하는 컬렉션(Collection)이 있다.
자바의 컬렉션에 대해 알아보자.
빅오 표기법
자료 구조에 대해 알기 전에, 먼저 빅오 표기법을 알고 있어야 한다.
빅오 표기법이란, 알고리즘 성능 분석의 수학적 표현 방식을 말한다.
자료 구조에서는 성능을 표현하기 위해 빅오 표기법을 사용한다.
빅오 표기법에서 중요한 것은 정확한 수치가 아닌 성능의 변화 추세에 초점을 둔다는 것이다.
'이 상황에서는 정확히 이 값이다' 라는 것이 아닌,
'이 정도면 이 쯤에서는 아마 이 정도의 값을 가지고 있겠다' 정도로 이해해야 한다.
배열
떠올리기 쉬운 대표적인 자료 구조의 첫번째로는 바로 배열이 있다.
배열은 '[]'를 사용해서 선언할 수 있다.
int[] numbers = new int[10]; // 사이즈 10의 배열 생성배열에는 index 번호가 있으므로 순서가 있고,
각 index에는 데이터가 중복으로 저장될 수 있다.
배열을 쉽게 이해하기 위해 놀이공원의 줄을 예시로 들어보자.
배열의 장점
배열은 index를 활용하여 간편하게 접근할 수 있다.
int findNumber = numbers[1]; // 1번째 index에 접근놀이공원의 줄에서 행운의 7번째 손님에게 프리패스권을 주기로 한다.
그러면 7번째 손님에게 바로 찾아가서 프리패스권을 부여하면 된다.
원하는 위치에 한번에 접근할 수 있으니, 성능은 O(1)이다.
배열의 단점
조회
배열은 조회에 상당한 시간이 걸린다.
원하는 데이터를 찾기 위해서는 각 index에 어떤 데이터가 들어있는지 하나하나 찾아봐야 한다.
=== 놀이공원 줄 line[5]에서 '김서방' 님 찾기 ===
// 1부터 탐색 시작
line[1] = "박서방"
line[2] = "홍서방"
line[3] = "이서방"
line[4] = "제갈서방"
line[5] = "김서방" // ** 찾았다! **하필 내가 찾고자 하는 데이터가 배열의 마지막에 있는 경우, 모든 index를 살펴봐야 한다.
따라서 성능은 배열의 크기 만큼인 O(n)이 된다.
데이터 추가 및 삭제
배열에서 데이터를 추가하려면 원하는 index에 공간을 만들어주어야 한다.
원래 해당 index에 있던 데이터부터 그 뒤의 모든 데이터들은 뒤로 한칸씩 물러나야 한다.
놀이공원의 줄에서 프리패스권을 사용한 손님이 등장하는 경우,
내가 서있던 곳이 1번째였다면, 2번째로 나의 index가 증가한다.
맨 앞에 데이터를 추가하는 최악의 상황의 경우,
첫번째부터 마지막까지 모든 데이터를 한칸씩 뒤로 이동해야 하기 때문에 성능은 O(n)이 되겠다.
정적 크기
int[] numbers = new int[10]; // 사이즈 10의 배열 생성배열을 생성할 때, 크기를 함께 설정한다.
이처럼 배열의 크기는 한번 설정하면 변경이 불가능하다.
처음에 사이즈를 크게 설정해서 공간이 여유로워도 줄일 수 없고,
갑자기 공간이 더 필요해도 늘릴 수 없다.
메모리를 유연하게 관리할 수 없다는 점이 배열의 치명적인 단점이다.
배열리스트(ArrayList)
단순 배열의 단점을 극복하기 위해 등장한 것이
바로 자바 컬렉션의 리스트 중 배열리스트(ArrayList)이다.
배열리스트는 순서가 있고 중복이 가능한 배열의 특징을 그대로 가지고 있으면서도,
정적 크기의 단점을 극복하여 동적으로 크기를 설정할 수 있다.
동적 크기
그렇다면 배열리스트는 어떻게 동적으로 크기를 조절할 수 있을까?
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
...
private static final int DEFAULT_CAPACITY = 10;
...
transient Object[] elementData; // non-private to simplify nested class access
...
} 사실 배열리스트의 내부를 살펴보면, 배열을 사용하고 있다.
배열을 사용하고 있으니, 배열의 크기도 생성과 동시에 설정해야 한다.
배열의 단점을 극복하는 것이 배열리스트인데, 똑같이 배열을 사용하면 어떻게 극복하는가?
배열리스트는 데이터를 조작하는 동안 사이즈를 초과하는 경우,
크기가 50% 증가한 새로운 배열을 생성해서 반환한다.
새로운 배열은 비어있을테니, 기존의 배열에서 새로운 배열에 데이터를 복사해서 반환한다.
(배열의 복사에는 System.arraycopy() 메서드를 사용한다.)
ArrayList<Integer> arrList = new ArrayList<>();또한, 배열리스트는 제네릭을 사용해서 타입 안전성을 확보할 수 있다.
배열리스트 단점
하지만 배열을 사용하기 때문에 동적으로 크기를 설정한다는 점도
메모리가 낭비될 수 있다는 근본적인 문제는 해결할 수 없으며,
여전히 데이터 조회, 추가 등에서 O(n)의 성능에 대한 단점을 극복하지 못했다.
배열리스트를 보완하는 다른 자료구조는 없을까?
연결리스트(LinkedList)
연결리스트는 배열과는 다르게 노드를 사용하는 리스트이다.
노드는 Data 그리고 연결된 노드들의 참조값을 가지고 있는 형태를 띄고 있다.
노드가 연결되어 있는 형태로, 배열과 동일하게
순서가 있으며 중복된 값을 포함할 수 있다는 특징을 가진다.
연결리스트 장점
연결리스트는 노드를 추가하고 삭제하면서 연결되는 노드의 참조값만을 변경하면 되기 때문에
초기에 크기를 설정할 필요도 없고, 메모리 낭비에 대한 걱정 없이 사이즈 최적화가 가능하다.
또한 자바의 연결리스트는 이중연결리스트로 구성되어,
맨 뒤의 데이터를 조작할 때에만 최적의 성능을 보이는 배열과는 달리
맨 앞 또는 맨 뒤의 데이터를 조작하는 경우 모두 최적의 성능을 가진다.
LinkedList<Integer> linkedList = new LinkedList<>();배열리스트와 마찬가지로 연결리스트는 제네릭을 사용해서 타입 안전성을 확보할 수 있다.
연결리스트 단점
사이즈 최적화로 메모리 낭비를 극복했음에도 불구하고,
데이터 조작은 아직 O(n/2)의 성능으로 한계를 벗어나지 못했으며,
조회의 경우 배열리스트와 비교했을 때 성능이 더 떨어졌다.
배열리스트의 단점을 완전히 극복했다고 하기에는 어렵다.
결론은 배열리스트(ArrayList)
애매한 부분이 많지만 어떻게 보면 연결리스트가 더 좋아보인다.
자료 구조의 맨 앞과 맨 뒤에서 접근이 가능하고,
메모리 낭비 없이 최적화된 사이즈를 사용할 수 있기 때문이다.
하지만 상대적으로 더 무거운 노드의 개념을 사용하고
배열리스트에서 사이즈 증가 및 이동 시 사용하는 데이터 복사 메서드,
System.arraycopy() 메서드가 아주 우수한 성능을 보여
전체적으로 성능은 배열리스트가 좋다.
자료 구조의 앞에서 데이터를 조작하는 일이 많은 경우 연결리스트를 사용하고
그 외에는 기본적으로 배열리스트를 사용하자!
마무리
얄팍하게 기억했던 자바의 리스트에 대해 살펴봤다.
실무에서는 ArrayList를 기본적으로 사용한다는 점을 기억하고,
데이터의 앞에서 수정이 자주 일어나면 LinkedList를 고려하자.
그리고 배열리스트와 연결리스트와는 다른 상황에서 사용되는 세트에 대해서도 잊지 말 것
