LinkedList
ArrayList vs LinkedList
기능은 ArrayList와 같지만 내부적으로 다르다.
ArrayList
- 메모리
- 고정 크기를 갖는다.
- 크기를 초과하면 새로 배열을 만들어야 하기 때문에 메모리 낭비가 심하다.
- 기존 배열은 가비지가 되기 때문에 가비지가 과다 생산된다.
- 속도
- 배열의 특징 상 인덱스를 이용하여 특정 항목을 찾을 때 속도 빠르다.
- 삭제할 때 이전 항목을 당겨와야 하기 때문에 속도가 느리다.
- 입력할 때 현재 항목을 다음 항목으로 이동해야 하기 때문에 속도가 느리다.
LinkedList
- 메모리
- 값을 넣을 때마다 새 메모리가 추가되는 가변 크기를 가진다.
- ArrayList 보다 메모리 낭비가 적고 가비지를 덜 생산한다.
- 속도
- 배열의 특징 상 인덱스를 이용하여 특정 항목을 찾을 때 속도 빠르다.
- 삭제할 때 이전 항목을 당겨와야 하기 때문에 속도가 느리다.
- 입력할 때 현재 항목을 다음 항목으로 이동해야 하기 때문에 속도가 느리다.
| ArrayList | LinkedList | |
|---|---|---|
| 장점 | - 메모리 낭비가 심하고 가비지가 과다 생산된다 - 검색이 빠르다 | - 메모리 낭비가 적고 가비지를 덜 생산한다 - 삽입/삭제 속도가 빠르다 |
| 단점 | - 삽입, 삭제 속도가 느리다 | - 검색이 느리다 |
LinkedList 구현
1단계: LinkedList 클래스 정의
1
public class MyLinkedList {}
2단계: 값을 담을 노드 클래스를 설계한다.
1
2
3
4
5
6
public class MyLinkedList {
static class Node {
Object value;
Node node;
}
}
- Node 클래스는 목록에서 각 항목의 값을 보관하는 객체로 역할을 한다.
- 여러 개의 MyLinkedList 객체가 공유하는 클래스이므로 static으로 Node 클래스를 설계한다.
3단계: 첫 번째 노드와 마지막 노드의 주소를 담을 필드, 목록 크기를 저장할 필드를 추가한다.
1
2
3
4
5
public class MyLinkedList {
Node first;
Node last;
int size;
}
값을 찾을 때는 첫 번째 노드부터 따라간다.
값을 추가할 때는 마지막 노드에 연결한다.
4단계
(1) Node의 생성자를 추가한다.
1
2
3
4
5
6
static class Node {
public Node(){}
public Node(Object value){
this.value = value;
}
}
(2) 목록에 값을 추가하는 add() 메서드를 정의한다.
1
2
3
4
5
6
7
8
9
10
11
12
public boolean add (Object element) {
Node node = new Node(element);
if (first == null) {
first = node;
} else {
last.next = node;
}
last = node;
size++;
return true;
}
5단계: 목록에서 값을 조회하는 get() 메서드를 정의한다.
1
2
3
4
5
6
7
8
9
10
11
public Object get (int index) {
if (index < 0 || index >= this.size) {
throw new IndexOutOfBoundsException();
}
Node cursor = first;
for (int = 0; i < index; i++) {
cursor = cursor.next;
}
return cursor.value;
}
6단계: 목록에서 특정 인덱스 위치에 값을 삽입하는 add(int, Object) 메서드를 정의한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public void add(int index, Object element) {
if (index < 0 || index > this.size) {
throw new IndexOutOfBoundsException();
}
Node node = new Node(element);
size++;
Node cursor = first;
for (int = 0; i < index - 1; i++) {
cursor = cursor.next;
}
if (node.next != null) {
node.next = cursor.next;
}
cursor.next = node;
}
7단계: 목록에서 특정 인덱스에 값을 제거하는 remove(int) 메서드를 정의한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public void remove(int index) {
if (index < 0 || index >= this.size) {
throw new IndexOutOfBoundsException();
}
size--;
if (index == 0) {
Node old = first;
first = old.next;
old.next = null;
return old.value;
}
Node cursor = first;
for (int = 0; i < index - 1; i++) {
cursor = cursor.next;
}
Node old = cursor.next;
cursor.next = old.next;
old.next = null;
return old.value;
}
8단계: 목록에서 특정 인덱스의 값을 바꾸는 set(int, Object) 메서드를 정의한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public Object set(int index, Object element) {
if (index < 0 || index >= this.size){
throw new IndexOutOfBoundsException();
}
Node cursor = first;
for (int = 0; i < index; i++) {
cursor = cursor.next;
}
Node old = cursor;
cursor.value = element;
return old.value;
}
9단계: 목록의 데이터를 새 배열에 담아 리턴하는 toArray() 메서드를 정의한다.
1
2
3
4
5
6
7
8
9
10
11
public Object[] toArray() {
Object[] arr = new Object[this.size];
Node cursor = this.first;
int = 0;
while(cursor != null) {
arr[i++] = cursor.value;
cursor = cursor.next;
}
return arr;
}
10단계: 인스턴스 필드에 대해 캡슐화를 적용한다. 목록 크기를 리턴하는 사이즈를 추가로 정의한다.
1
2
3
4
5
6
7
private Node first;
private Node last;
private int size;
public int size() {
return this.size;
}