MyLinkedList 만들기
1단계: LinkedList 클래스 정의
1
public MyLinkedList {}
2단계: 값을 담을 노드 클래스 설계
- Node의 인스턴스 필드와 생성자를 정의하자.
1
2
3
4
5
6
7
8
9
10
11
public class MyLinkedList {
static class Node {
Object value;
Node next;
Node(){}
Node(Object value) {
this.value = value;
}
}
}
3단계: 필드 추가
- 첫 번째 노드와 마지막 노드의 주소를 담을 필드를 추가한다.
- 목록 크기를 저장할 필드를 추가한다.
1
2
3
4
5
6
7
8
9
10
public class MyLinkedList {
Node first;
Node last;
public int size;
static class Node {
Object value;
Node next;
}
}
다음 단계부터 LinkedList의 메서드를 정의할 것이다.
다음과 같은 LinkedList가 있다고 가정해보자.
4단계: add(Object) 메서드를 정의
- 목록에 값을 추가하는
boolean add(Object e)
메서드를 정의한다.
1
2
3
4
5
6
public boolean add (Object element) {
Node node = new Node(element);
last.next = node;
last = node;
size++;
}
5단계: get(int) 메서드 정의
- 목록에서 값을 조회하는
Object get(int index)
메서드를 정의한다.
1
2
3
4
5
6
7
8
9
10
public Object get(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("인덱스가 유효하지 않습니다.");
}
Node cursor = first;
for (int i = 1; i <= index; i++) {
cursor = cursor.next;
}
return cursor.value;
}
6단계: add(int, Object) 메서드 정의
- 목록에서 특정 인덱스 위치에 값을 삽입하는
void add(int, Object)
메서드를 정의한다.
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
26
public void add(int index, Object element) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("인덱스가 유효하지 않습니다.")
}
Node node = new Node(element);
size++;
if (index == 0) {
node.next = first;
first = node;
return;
}
Node cursor = first;
for (int i = 1; i <= index - 1; i++) {
cursor = cursor.next;
}
node.next = cursor.next;
cursor.next = node;
if (node.next == null) {
last = node;
}
}
7단계: remove(int) 메서드 정의
- 목록에서 특정 인덱스의 값을 제거하는
Object 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
26
27
28
29
public Object remove (int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("인덱스가 유효하지 않습니다.");
}
size--;
if (index == 0) {
Node old = first;
first = node.next;
old.next = null;
return old.value;
}
Node cursor = first;
for (int i = 1; i < index - 1; i++) {
cursor = cursor.next;
}
Node old = cursor.next;
cursor.next = old.next;
old.next = null;
if (cursor.next == null) {
last = cursor;
}
return old.value;
}
8단계: set(int, Object) 메서드 정의
- 목록에서 특정 인덱스의 값을 바꾸는
Object set(int, Object)
메서드를 정의한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
public Object set(int index, Object element) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("인덱스가 유효하지 않습니다.");
}
Node cursor = first;
for (int i = 1; i <= index; i++) {
cursor = cursor.next;
}
Object old = cursor.value;
cursor.value = element;
return old;
}
10단계: toArray() 메서드를 정의한다.
- 목록의 데이터를 새 배열에 담아 리턴하는
toArray()
메서드를 정의한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
public Object[] toArray() {
Object[] arr = new Object[this.size];
int i = 0;
Node cursor = first;
while (cursor != null) {
arr[i++] = cursor.value;
cursor = cursor.next;
}
return arr;
}
11단계: size() 메서드를 정의한다.
- 목록의 크기를 저장하는 필드
size
를size()
메서드로만 접근할 수 있게private
으로 전환한다. - 클래스 내부에서만 쓰이는
first
,last
필드도private
으로 전환한다.
1
2
3
public int size() {
return this.size;
}
1
2
3
4
5
public class MyLinkedList {
private Node first;
private Node last;
private int size;
}
(단계 추가 예정)