첫번째 자료구조로 가장 간단한 형태의 리스트에 대해서 배워보겠습니다.
1. 리스트란?
리스트는 선형적인 자료구조 중의 하나로서 데이터를 일렬로 늘여 놓은 형태입니다. 그렇기 때문에 리스트는 순서를 가진다는 특징이 있습니다.
모든 언어를 사용하든 간에 가장 기본적으로 배우게 되는 메모리 공간 형태이며 자료형(Data Type)이 둘 이상의 값을 저장할 수 있습니다.(다만, Python은 예외)
이곳에서는 리스트를 어떻게 생성하고 어떻게 사용하는 지 보다는 리스트라는 자료구조에서 데이터를 어떻게 다루는 지에 대해 더 알고 싶기 때문에 이번 챕터에서는 리스트를 관리를 할 때 중요한 기능 3가지를 다루어 보겠습니다.
- 데이터 삽입하기
- 데이터 삭제하기
- 리스트 탐색하기
이 3가지는 어떤 데이터 구조를 다룰 때도 항상 중요한 요소이기 때문에 앞으로 이에 대해 초점을 맞춰 진행을 해 보도록 하겠습니다.
2. 리스트의 종류
- ArrayList
- LinkedList
- Single Linked List
- Double Linked List
리스트의 종류는 위와 같습니다. 먼저 ArrayList가 무엇인지 알아보도록 합시다.
3. ArrayList
단어 뜻 그대로 배열 기반의 리스트로 메모리 공간을 연속적으로 사용합니다. 배열 기반의 구조이기 때문에 배열과 동일한 인덱스를 사용하고 인덱스를 이용한 데이터 접근은 배열의 크기가 아무리 크더라도 인덱스로 접근을 하게되면 값을 찾는데 항상 동일한 시간이 걸립니다.
-> O(1)
ArrayList는 컴퓨터의 실제 메모리 공간에서도 연속적인 공간를 사용하고 있기 때문에 컴퓨터가 연산하기 쉬운 구조로 되어있습니다. (다음 데이터에 접근하기 쉽기 때문)
그렇기 때문에 이전 인덱스에서 다음 인덱스로 접근하는 속도가 매우 빠르죠.
반면, LinkedList는 뒤에서 더 설명하겠지만 데이터를 논리적으로 연결시켜서 마치 연결된 것처럼 사용할 수는 있지만 실제 컴퓨터 메모리 공간 상에서는 연속적인 공간을 차지하고 있는 것이 아니기 때문에 데이터 간의 이동 시간 자체는ArrayList보다 느릴 수 있습니다.
추가
이 그림은 크기가 7인 ArrayList를 시각화 한 모습입니다. 현재 0번부터 2번 index까지 각 데이터가 한 자리씩을 차지하고 있습니다.
데이터가 추가 될 때는 반드시 위 그림과 같이 가장 마지막으로 채워져 있던 2번 index의 바로 옆에 3번 index자리에 데이터가 추가됩니다.
따라서 리스트에서 데이터의 추가라는 것은 추가하고 싶은 데이터를 리스트의 가장 마지막으로 채워진 index 바로 뒤에 데이터를 삽입하는 것을 말합니다.
삽입
추가와 달리 데이터의 삽입은 데이터를 맨 뒤에 추가하는 개념이 아닌 내가 원하는 위치에 데이터를 삽입하는 것으로 데이터가 이미 들어가 있더라도 해당 index의 데이터와 그 뒤의 데이터들을 전부 뒤로 밀고 그 자리에 데이터가 삽입되는 형태를 말합니다.
그런데 이때 데이터를 한칸씩 밀어주는 과정에서 만약 데이터가 매우 많다면 많은 만큼의 시간이 소요가 되므로 미는 과정은 O(N)의 시간 복잡도를 가진다고 말할 수 있습니다.
주의할 점
삽입의 경우 추가하고자 하는 index에 데이터를 아무런 과정없이 그냥 넣게 되면 기존에 있던 데이터는 사라지게 되므로 데이터 손실이라는 매우 중요한 결함이 생기게 되기 떄문에 이에 유의하여 삽입을 사용해야 합니다.
삭제
index 기반의 데이터 삭제를 할 때에도 데이터를 이동시켜주는 작업이 반드시 필요합니다.
만약 2번 index를 삭제하고자 했을 때,
위와 같이 아무런 과정을 진행하지 않으면 이 ArrayList는 중간이 뻥 뚫리게 되는 구조를 가지게 되므로 이 경우 오류가 발생할 것입니다. 그래서 빈 공간을 뒤의 데이터를 당겨오면서 메꿔 주어야 합니다.
그러면, 그 결과 위 그림처럼 빈 공간 없이 List에 데이터가 나열된 모습을 보실 수 있습니다.
검색 by index
마지막으로 index에 의한 검색 과정을 보겠습니다.
ArrayList는 Random access로 해당 index에 직접 접근하게 된다. 데이터가 아무리 많아져도 해당 index에 직접적으로 접근하는 것이기 때문에 이에 대한 탐색 속도는 매우 빠르고 이렇듯 데이터 갯수와는 상관없이 소요시간이 일정하다면 이런 경우에는 O(1)의 시간 복잡도를 갖습니다.
4. 시간 복잡도
다음은 ArrayList의 시간 복잡도입니다.
데이터를 읽기만 할 때는 항상 똑같은 시간이 소모됨을 확인 할 수 있습니다. 반면, 데이터를 추가하거나 삭제할 때는 굉장히 느린 것을 보실 수 있습니다.
이는 다음에 배울 LinkedList와는 정반대인 것을 알게될 것입니다.
| 연산 | 평균 시간 | 최악의 시간 |
| read(get) | O(1) | O(1) |
| insert | O(n) | O(n) |
| delete | O(n) | O(n) |
| search | O(n) | O(n) |
5. ArrayList 실습
ArrayList를 구현하기 위한 list interface를 구현해 봅시다.
package list;
public interface IList<T> {
void add(T t);
void insert(int index, T t);
void clear();
boolean delete(T t);
boolean deleteByIndex(int index);
T get(int index);
int indexOf(T t);
boolean isEmpty();
boolean contains(T t);
int size();
}IList라는 인터페이스를 선언하여 List의 기능을 확인할 각 메소드의 프로토타입들을 선언한 부분입니다.
package list;
publick class MyArrayList<T> implements IList<T> {
...
}MyArrayList 파일은 위에서 선언한 인터페이스를 구현 상속한 클래스입니다. 또한 리스트 안의 데이터 타입은 정해두지 않았기 때문에 제네릭 타입으로 설정하였습니다.
앞으로 모든 자료구조 구현에서는(그래프 제외) 제네릭 타입으로 데이터를 받아 올 것입니다. 그 이유는 다음과 같은 것들이 있습니다.
- 자료 구조에는 어떤 타입이 들어가도 되기 때문임.
- 그래프는 구현 방식이 어려워 정수 타입만 받도록 할 것임.
위 코드를 타이핑하면 프로그램 기능으로 IList에 있는 구현되지 않은 메소드들의 바디가 자동완성으로 불러올 수 있습니다.
멤버변수
private int size;
private T[] elements;MyArrayList의 멤버변수로는 데이터를 저장할 수 있는 T타입의 배열 element와 구현의 편의성을 위해 배열의 size를 관리해야 하는데 이를 제어할 수있는 변수 size를 선언합니다.
생성자
private static final int DEFAULT_SIZE = 50;
public MyArrayList() {
this.size = 0;
this.elements = (T[]) new Object[DEFAULT_SIZE];
}MyArrayList가 생성되는 시점의 생성자 코드를 생성하는 단계입니다.
초기화 될 때는 아무런 값도 있지 않을 것이기 때문에 size는 0으로 초기화 해 주고 element에는 DEFAULT_SIZE, 즉 50의 크기를 가지는 배열 객체를 생성하여 저장합니다.
- 여기서 배열의 크기를 밖에서 DEFAULT_SIZE로 선언하고 실제 메서드 안에서 이것을 사용한 이유는 배열의 크기를 바꾸어야 하는 상황이 생길 때, 해당 하는 변수를 일일히 하나하나 전부 바꾸어 주는 불편함을 해소하는 것처럼 코드의 유지보수 측면에서 더 높은 효율을 가지기 때문입니다.
add
@Override
public void add(T t) {
if(this.size == this.elements.length) {
this.elements = Arrays.copyOf(this.elements, this.size*2)
}
this.elements[this.size++] = t;
}배열에 element를 추가할 때는 인덱스로 접근하여 그곳에 그대로 대입합니다.
위에서 배웠듯이 ArrayList의 추가는 배열의 현재 위치(빈 공간)에 추가를 하고 현재위치를 바로 그 다음 위치(빈 공간)로 넘기면 되기 때문에 인덱스를 this.size로 설정합니다.
위치를 옮기는 과정은 this.size++로 배열의 인덱스를 1만큼 증가시키면 됩니다.
- 그래서 size의 위치는 항상 비어있는 위치 중 가장 첫 번째 위치인 것입니다.
단, 배열이 꽉 차있는 경우 더 이상 데이터를 추가할 곳이 없습니다. 즉, 배열의 인덱스로 지정한 size가 배열의 크기보다 커지기 때문에 오류가 발생할 수 있는데, 이 경우에 if문으로 구별하여 해당 배열을 자바의 Arrays.copyOf() 메소드를 통해 원하는 크기로 복사를 진행 합니다.
- 위 코드에서는 size의 두 배 크기로 재조정하여 다시 element에 이전 배열을 복사하였습니다.
insert
@Override
public void insert(int index, T t); {
for (int i = index; i < this.size; i++) {
this.elements[i + 1] = this.elements[i];
}
this.elements[index] = t;
this.size++
}
insert같은 경우는 배열 인덱스의 정보도 필요하고 해당 인덱스부터 현재 위치 전까지의 모든 데이터들을 한 칸씩 미루어 넣는 과정도 필요합니다. 그리고 원하는 인덱스를 배열의 인덱스로 하여 그곳에 인자로 받아온 데이터 t 를 넣고 현재 위치를 1만큼 늘려 갱신합니다.
deleteByindex
@Override
public boolean deleteByindex(int index){
if(index < 0 || index > this.size - 1){
return false
}
for (int i = index; i < this.size - 1; i++){
this.elements[i] = this.elements[i+1];
}
this.size--;
return true;
}index에 의한 delete 과정을 진행할 때는 해당 index부터 현재위치를 의미하는 size의 바로 전전칸까지 데이터를 한 칸씩 앞당겨오는 과정을 진행해야 합니다.
- for 문에서 반복 범위가 i < this.size - 1 인 이유는 -1이 붙어있지 않다면 뒤의 데이터를 앞당겨 와야하는 과정에서 size는 빈 공간을 의미하는데 빈 공간의 데이터를 당겨올 수는 없기 때문입니다.
삭제가 잘 이루어졌다면 size를 -1해주고 true를 리턴합니다.
반면, index가 음수인 경우이거나 메소드 호출 시 지정한 index변수가this.size - 1 보다 크게 되는 경우 위에서 지적한 문제가 발생하기 때문에 별도의 if문으로 구별하여 false를 리턴합니다.
delete
@Override
public boolean delete(T t) {
for (int i = 0; i < this.size; i++) {
if(this.elements[i].equals(t)) {
for (int j = i; j < this.size - 1; j++) {
this.elements[j] = this.elements[j + 1];
}
this.size--;
return true;
}
}
return false;
}element값을 받아 삭제하는 경우는 리스트 안의 모든 원소를 순회하면서 해당하는 원소를 찾아야 하기 때문에 먼저 for문으로 데이터를 하나씩 순회합니다.
그리고 중간에 만약 인자로 받아온 t와 현재 돌고 있는 배열의 element의 값이 일치하면 현재 for문이 지정하고 있는 i가 삭제를 해야하는 index 이므로 그 값부터 시작하여 다시 for문을 통해 위 deleteByindex 에서 진행했던 밀어주기 과정을 진행합니다.
get
@Override
public T get(int index){
if(index < 0 || index > this.size - 1){
throw new IndexOutOfBoundsException();
}
return this.elements[index];
}get은 비교적 간단합니다. 기본적으로 T 타입의 원소를 반환해 주는데 그 값 인자로 받아온 index에 의해 접근되는 리스트의 value를 리턴하면 됩니다.
index의 범위가 이전의 deleteByindex에서 발생한 문제와 똑같은 상황이 발생하지 않도록 예외처리 또한 해 줍시다.
- T타입을 반환하는 메소드이기 때문에 예외 상황에서 false를 리턴하지 않고 위와 같이 예외 문구를 throw 할 수도 있습니다.
contains
@Override
public boolean contains(T t) {
for (int i = 0; i < this.size ;i++) {
if(this.elements[i].equals(t)) {
return true;
}
}
return false;
}contains() 메소드는 리스트를 순회하면서 인자로 받아온 데이터가 해당 리스트 안의 원소인지 아닌지를 판별하는 메소드입니다.
그 동안 했던 것과 마찬가지로 반복문을 통해 리스트 데이터를 하나씩 돌면서 equals 메소드로 리스트의 원소와 일치하면 true(=1) 아니면 false(=0)을 반환해 주는 logic을 구현합니다.
indexOf
@Override
public boolean indexOf(T t) {
for (int i = 0; i < this.size ;i++) {
if(this.elements[i].equals(t)) {
return i;
}
}
return -1;
} indexOf() 메소드는 위의 contains 메소드와 거의 동일한 과정으로 리스트를 돌면서 인자로 받아온 데이터가 반복문을 돌던 중 해당 element와 일치한다면 현재 for문의 i 즉, 현재 index를 반환합니다.
- 만약 리스트 안의 원소가 아닐 경우, 즉 for문을 돌아도 반환되는 값이 없는 경우 -1을 반환하는데 그 이유는 만약, 0을 반환하게 되면 배열의 0번 index로 인식하여 원치않은 결과를 발생시킬 수 있기 때문입니다.
size
@Override
public int size() {
return this.size;
}다른 기능 구현의 편의를 위해서, 선언했던 size 변수의 값은 현재 리스트의 크기를 알려주는 것이기 때문에 이를 리턴하는 size 메소드도 구현하였습니다.
isEmpty
@Override
public boolean isEmpty() {
return this.size == 0;
}isEmpty 메소드는 리스트가 비어있는 지 아닌 지를 판별하는 메소드로 비어있다면 1(=true) 그렇지 않다면 0(=false)을 리턴하므로 'this.size == 0' 을 리턴하면 이 logic이 매우 간단하게 해결됩니다.
clear
@Override
public void clear() {
this.size = 0;
this.elements = (T[]) new Object[DEFAULT_SIZE];
}clear는 리스트 안의 원소를 모두 비우는 것인데 사실상 배열을 새로 만드는 생성자의 역할과 동일한 기능을 수행하는 것이기 때문에 생성자에서 했던 것과 똑같은 과정을 작성하면 됩니다.
6. 자료구조 시간 복잡도 비교
- 평균 시간 복잡도(Average)
| 자료구조 | Access | Search | Insertion | Deletion |
| Array | Θ(1) | Θ(n) | Θ(n) | Θ(n) |
| Stack | Θ(n) | Θ(n) | Θ(1) | Θ(1) |
| Queue | Θ(n) | Θ(n) | Θ(1) | Θ(1) |
| Singly Linked List | Θ(n) | Θ(n) | Θ(1) | Θ(1) |
| Doubly Linked List | Θ(n) | Θ(n) | Θ(1) | Θ(1) |
| Hash Table | Θ(1) | Θ(1) | Θ(1) | Θ(1) |
| Binary Search Tree | Θ(log2n) | Θ(log2n) | Θ(log2n) | Θ(log2n) |
| AVL Tree | Θ(log2n) | Θ(log2n) | Θ(log2n) | Θ(log2n) |
| B Tree | Θ(log2n) | Θ(log2n) | Θ(log2n) | Θ(log2n) |
- 최악의 경우 시간 복잡도(Worst)
| 자료구조 | Access | Search | Insertion | Deletion |
| Array | O(1) | O(n) | O(n) | O(n) |
| Stack | O(n) | O(n) | O(1) | O(1) |
| Queue | O(n) | O(n) | O(1) | O(1) |
| Singly Linked List | O(n) | O(n) | O(1) | O(1) |
| Doubly Linked List | O(n) | O(n) | O(1) | O(1) |
| Hash Table | O(n) | O(n) | O(n) | O(n) |
| Binary Search Tree | O(log2n) | O(log2n) | O(log2n) | O(log2n) |
| AVL Tree | O(n) | O(n) | O(n) | O(n) |
| B Tree | O(log2n) | O(log2n) | O(log2n) | O(log2n) |
7. 정리
이로써 MyArrayList라는 클래스에서 배열을 이용하여 리스트를 구현한 ArrayList의 수많은 기능을 모두 구현해 보았습니다. 자료구조 및 알고리즘은 메소드 사용 방법을 공부하는 과목이 아닙니다. 그렇기 때문에 그 안의 메소드들을 하나하나 직접 구현해 보면서 작동하는 원리를 직접 습득해야 알고리즘을 구현하기 훨씬 쉬워질 것입니다. 다음시간에는 리스트의 구현 방법 중 LinkedList에 대해서 알아보도록 하겠습니다.
긴 글 읽어주셔서 감사합니다.
'CS 지식 > 자료구조와 알고리즘(Java)' 카테고리의 다른 글
| [자료구조 | Java] Stack(스택) (0) | 2022.12.28 |
|---|---|
| [자료구조 | Java] Double LinkedList(이중 연결 리스트) (0) | 2022.12.27 |
| [자료구조 | Java] LinkedList(연결 리스트) 이론 및 구현 (2) | 2022.12.27 |
| [자료구조 | Java] 자료구조와 알고리즘 기초 (0) | 2022.12.27 |
| [자료구조&알고리즘 with Java] 자료구조 및 알고리즘 시작 (0) | 2022.12.26 |
