...
Doubly LinkedList 자료구조
- 노드(객체)를 연결하여 리스트 처럼 만든 컬렉션 (배열이 아님)
- 노드들을 연결하여 목록을 구성하기에 용량(capacity) 개념이 없다. (무한정 저장 가능)
- 데이터의 저장순서가 유지되고 중복을 허용한다.
- ArrayList 처럼 인덱스로 요소를 접근하지만, 배열이 아니기 때문에 별도로 탐색시간이 걸려 임의의 요소에 대한 접근 성능은 좋지 않다.
- 대신 데이터의 중간 삽입, 삭제가 빈번할 경우 빠른 성능을 보장한다.
- 하지만 노드에 들어있는 게 많은 만큼 메모리의 사용량이 많아진다는 단점이 있다.
Singly LinkedList는 단방향 연결 리스트이기 때문에 만일 리스트의 끝 요소를 탐색하려면, 처음(head)부터 끝까지 순회하며 탐색해야 하지만, Doubly LinkedList는 prev 포인트를 가지고 있기 때문에 한번에 마지막 요소를 탐색이 가능하다. 그래서 실무에서 사용하는 LinkedList 형태는 기본적으로 Doubly Linked List 이다.
[JCF] 🧱 LinkedList 구조 & 사용법 - 정복하기
LinkedList 컬렉션 자바의 Linked List는 ArrayList와 같이 인덱스로 접근하여 조회 / 삽입이 가능하지만 내부 구조는 완전히 다르게 구성되어 있다는 점이 특징이다. ArrayList는 내부적으로 배열을 이용하
inpa.tistory.com
Doubly LinkedList 실전 구현하기
우선 더블 연결(Linked) 리스트를 구현하기 앞서 먼저 싱글 연결 리스트를 구현하는 연습을 해보고 오는 것을 추천한다. 연결(Linked) 리스트의 'linked' 개념이 어떤식으로 노드끼리 연결되고 끊어지는 원리를 가장 간단한 Singly Linked List를 통해 먼저 숙지한다면 Doubly Linked List를 구현하는데 있어 수월해질 수 있다.
클래스 필드 & 생성자 정의하기
- head : 리스트의 가장 첫 노드를 가리키는 포인트로 이용될 변수
- tail : 리스트의 가장 마지막 노드를 가리키는 포인트로 이용될 변수
- size : 리스트에 있는 요소의 개수(연결 된 노드의 개수)
public class MyDoublyLinkedList<E> {
private Node<E> head; // 노드의 첫 부분을 가리키는 레퍼런스
private Node<E> tail; // 노드의 끝 부분을 가리키는 레퍼런스
private int size; // 리스트 요소 갯수
// 생성자
public MyDoubleLinkedList() {
this.head = null;
this.tail = null;
this.size = 0;
}
// ...
}
head 와 tail 개념이 필요한 이유
그냥 노드만 next로 서로 참조하여 연결하면 되지 head와 tail이라는 개념이 필요한 이유는 가장 처음 요소와 가장 마지막 요소에 대한 링크를 표현하기 위해서이다. 하나의 노드는 다음 노드 정보만 가지고 있기 때문에, 가장 첫번째 노드를 참조하고 있는 포인트를 만들필요가 있고 그것이 head이다. 마지막 노드는 tail 이다.
또한 뒤에서 배울 addLast() 메서드 같은경우 요소를 맨마지막에 추가해줄때 tail이 없다면 add 할때마다 맨마지막 요소가 어디까지인지 알길이 없기 때문에 맨날 노드들을 처음 부터 순회해야 할지도 모른다.
노드 클래스 정의하기
LinkedList의 경우 ArrayList와 가장 큰 차이점이라 한다면 바로 '노드(Node)'라는 객체를 이용하여 연결한다는 점이다.
노드는 대단한 건 아니고 그냥 객체 이다. 이 클래스에는 자료를 저장할 Data 라는 필드와 다음/이전 연결 요소의 주소를 저장하는 Next 와 Prev 라는 필드를 가지고 있을 뿐이다. 이 노드 객체들이 서로 쌍방 연결된 형태가 Doubly Linked List 인 것이다.
전 시간에 구현해본 ArrayList의 경우 오브젝트 배열(Object[])을 사용하여 데이터를 담아두었다면, LinkedList 는 여러 노드 객체들을 내부적인 처리로 체인(chain)처럼 연결한다.
위의 노드 객체를 클래스로 구현해보면 코드는 다음과 같다.
public class MyDoublyLinkedList<E> {
// ...
// inner static class
private static class Node<E> {
private E item; // Node에 담을 데이터
private Node<E> next; // 다음 Node 객체를 가르키는 래퍼런스
private Node<E> prev; // 이전 Node 객체를 가르키는 래퍼런스
// 생성자 (이전 노드 포인트 | 데이터 | 다음 노드 포인트)
Node(Node<E> prev, E item, Node<E> next) {
this.item = item;
this.next = next;
this.prev = prev;
}
}
}여기서 눈여겨 봐야 할 점은 세가지 이다.
- 왜 클래스 안에다 클래스를 선언하였는가?
- 왜 private 접근 지시자인가?
- 왜 static이 붙었는가?
물론 Node 클래스를 MyDoublyLinkedList 클래스 밖에서 선언해도 문제는 없다. 다만 Node 클래스는 오로지 MyDoublyLinkedList 클래스에서만 이용되며, 다른 클래스에서는 전혀 이용되지 않는다.
이때 내부 클래스로 선언해주면 여러가지 장점을 얻게 되는데 이에 대해선 내부 클래스의 장점 포스팅을 참고하길 바란다.
그리고 private 접근제어자의 경우 객체가 외부로 노출되면 보안상의 문제가 발생할 수 있기 때문에 오로지 MyDoublyLinkedList 메소드로만 제어가 가능하도록 하기위해 설정하였다.
마지막으로 내부 클래스면 내부 클래스지 static으로 선언한 이유는 메모리 폭발(memory leak) 이슈 때문에 그렇다. 이에 대해선 내부 클래스는 static 으로 선언하라 포스팅을 참고하길 바란다.
선수로 Singly Linked List를 보고 온 독자분들이라면, 싱글 링크드의 노드 클래스 구성과 비교하면 그저 prev 변수만 추가된 것을 볼 수 있다.
이렇게 양방향으로 연결되면 무엇이 좋은가? 라고 묻는다면, Singly Linked List에 비해 검색(색인)능력이 좋아지게 된다.
단방향으로 연결 된 Singly LinkedList의 경우 마지막 요소를 얻기 위해서는 head부터 시작하여 탐색하여야 한다. 물론 따로 tail이라는 끝점을 두어 어느정도 극복을 했지만, 요소를 remove하는데 있어 결국 한계점에 봉착하고 말았다.
그대신 Doubly Linked List의 경우는 이전 노드를 가리키는 변수를 갖고 있기 때문에 tail부터 거꾸로 탐색할 수 있어, 만일 찾으려는 노드가 tail에 가깝다면 역순으로, head에 가깝다면 순차적으로 탐색하면 되기 때문에 좀 더 효율적인 탐색이 가능해진다.
search 구현하기
본격적인 연결 리스트의 동작 add와 remove를 구현하기 앞서 따로 내부 메소드 용으로 search()를 구현하고자 한다.
리스트에 add와 remove를 하기 위해선 우선추가 / 삭제할 요소 탐색이 우선이 되기 때문에 반복적으로 재사용되므로 따로 내부 메소드로 분리한다. 이때 보다 효율적인 탐색을 위해 탐색 방향을 두가지로 나눌 것이다.
- 만일 인덱스가 0(처음)에 가깝다면 순차 방향 탐색
- 만일 인덱스가 size(마지막)에 가깝다면 역 방향 탐색
이런식으로 구현해놓으면 요소를 검색할때 시간복잡도를 좀더 줄일수 있다는 장점이 있다.
private Node<E> search(int index) {
Node<E> n; // 반환할 노드
if ((size / 2) > index) {
// 1. 만일 인덱스가 시작에 가까우면, 순차 탐색
n = head;
for (int i = 0; i < index; i++) {
n = n.next;
}
} else {
// 2. 만일 인덱스가 끝에 가까우면, 역순 탐색
n = tail;
for (int i = size - 1; i > index; i--) {
n = n.prev;
}
}
return n;
}이때 반복문 범위를 index 까지 탐색이 아닌 index 전까지만 탐색되어야 하는데, 반복문의 범위가 i <= index 가 아닌 i < index 이유는 노드의 next 자체가 그 다음 노드를 가리키기 때문이다. prev도 마찬가지로 index 후까지만 탐색한다.
실제 자바의 LinkedList 클래스에서는private Node<E> node(int index)메소드명으로 구현되어있지만, 이해하기 쉽게 search 라는 메소드명으로 명명하였다.
add 구현하기
자바의 LinkedList 클래스의 add 메서드 종류를 보면 다음과 같이 4가지가 존재한다.
- void addFirst(Object obj) : 첫번째 위치에 요소 추가
- void addLast(Objec obj) : 마지막 위치에 요소 추가
- boolean add(Object obj) : 마지막 위치에 요소 추가 (성공하면 true)
- void add(int index, Object element) : 지정된 위치에 요소 추가
addFirst 구현
public void addFirst(E value) {
// 1. head를 임시 백업함
Node<E> first = head;
// 2. 새 노드를 추가 (이때 첫번째 노드니까 prev는 null이 되고 next는 head가 가리키는 노드가 되게 된다)
Node<E> new_node = new Node<>(null, value, first);
// 3. 노드를 추가하였으니 리스트 크기 증가
size++;
// 4. 첫번째 기준이 변경되었으니 head를 삽입된 새 노드로 참조하도록 업데이트
head = new_node;
if (first == null) {
// 5. 만일 빈 리스트에서 최초의 요소 추가였을 경우, tail도 첫째 노드를 바라보도록 업데이트
tail = new_node;
} else {
// 6. 만일 빈 리스트가 아닐경우, 추가되기 이전 첫번째이었던 노드에서 prev를 새 노드로 참조하도록 업데이트
first.prev = new_node;
}
}
1. 먼저 빈 리스트가 다음과 같이 존재한다. (비어있으니까 head와 tail은 각각 null이다)
2. 새 노드를 추가한다. 이때 최초의 노드이기 때문에 next와 prev 는 null 이 된다.
3. first 변수의 값이 null 이므로 head와 tail 모두 새 노드를 바라보도록 업데이트 한다.
4. 이번엔 빈 리스트가 아닌 요소가 들어있는 리스트에 노드를 addFirst 하려고 한다. 우선 head가 가리키는 노드@50 을 first 변수에 백업한다.
5. 새 노드를 추가하면서 동시에 next가 @50을 가리키게 된다. (첫번째니까 prev는 null)
6. head를 새 노드를 가리키도록 업데이트 한다(@50 → @40)
7. first(@50) 노드의 prev를 새 노드를 가리키도록 업데이트한다.
8. 최종적으로 이렇게 양방향으로 노드 끼리 연결되는 리스트가 구성되게 된다.
addLast 구현
public void addLast(E value) {
// 1. tail를 임시 백업함
Node<E> last = tail;
// 2. 새 노드를 추가 (이때 마지막 노드니까 next는 null이 되고 prev는 tail이 가리키는 노드가 되게 된다)
Node<E> new_node = new Node<>(last, value, null);
// 3. 노드를 추가하였으니 리스트 크기 증가
size++;
// 4. 마지막 기준이 변경되었으니 tail를 삽입된 새 노드로 참조하도록 업데이트
tail = new_node;
if (last == null) {
// 5. 만일 빈 리스트에서 최초의 요소 추가였을 경우, head도 첫째 노드를 바라보도록 업데이트
head = new_node;
} else {
// 6. 만일 빈 리스트가 아닐경우, 추가되기 이전 마지막이었던 노드에서 next를 새 노드로 참조하도록 업데이트
last.next = new_node;
}
}
1. 먼저 빈 리스트가 다음과 같이 존재한다. (비어있으니까 head와 tail은 각각 null이다)
2. 새 노드를 추가한다. 이때 최초의 노드이기 때문에 next와 prev 는 null 이 된다.
3. last 변수의 값이 null 이므로 head와 tail 모두 새 노드를 바라보도록 업데이트 한다.
4. 이번엔 빈 리스트가 아닌 요소가 들어있는 리스트에 노드를 addLast 하려고 한다. 우선 tail이 가리키는 노드@50 을 last 변수에 백업한다.
5. 새 노드를 추가하면서 동시에 tail이 @50을 가리키게 된다. (마지막이니까 next는 null)
6. tail을 새 노드를 가리키도록 업데이트 한다(@50 → @60)
7. last(@50) 노드의 next를 새 노드를 가리키도록 업데이트한다.
8. 최종적으로 이렇게 양방향으로 노드 끼리 연결되는 리스트가 구성되게 된다.
add 구현
add()의 동작은 addLast() 와 같다. 실제로 LinkedLIst API를 보면 add 메소드를 호출하면 addLast()를 호출한다.
public boolean add(E value) {
addLast(value);
return true;
}
add 중간 삽입 구현
중간 삽입을 하려면 인덱스 위치를 외부로 부터 받아야하기 때문에 가장 먼저 인덱스 범위를 체크해야 하는 것을 잊지말자. 그리고 중간 삽입의 포인트는 추가하려는 위치의 이전 노드(prev_node) 와 다음 노드(next_node) 참조값을 변수에 백업하는 것이 핵심이다.
public void add(int index, E value) {
// 1. 인덱스 범위 체크
// 인덱스가 0보다 작거나 size 보다 클 경우 에러
// (인덱스가 size보다 크면 마지막 요소 다음 빈공간의 다음 빈공간을 가리키는 거니까)
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
}
// 2. 추가하려는 index가 0이면 addFirst 호출
if(index == 0) {
addFirst(value);
return;
}
// 3. 추가하려는 index가 size와 같으면 addLast 호출
if(index == size) {
addLast(value);
return;
}
// 4. 추가하려는 위치의 다음 노드 얻기
Node<E> next_node = search(index);
// 5. 추가하려는 위치의 이전 노드 얻기
Node<E> prev_node = next_node.prev;
// 6. 새 노드 생성 (바로 이전 / 다음 노드와 연결됨)
Node<E> new_node = new Node<>(prev_node, value, next_node);
// 7. 노드를 추가하였으니 리스트 크기 증가
size++;
// 8. 이전 노드의 next를 새 노드에 연결
prev_node.next = new_node;
// 9. 다음 노드의 prev를 새 노드에 연결
next_node.prev = new_node;
}만일 index가 1인 위치(@200번지)에 노드를 삽입한다고 가정한다면 add 중간 삽입 과정은 다음과 같다.
1. 추가하려는 위치의 이전 노드(prev_node) 와 다음 노드(next_node)를 임시 저장
2. 새 노드 생성 (생성하며 동시에 이전 / 다음 노드에 각각 연결)
3. 이전 노드의 next 참조를 추가된 새 노드에 연결
4. 다음 노드의 prev 참조를 추가된 새 노드에 연결
remove 구현하기
LinkedList의 remove 메서드에는 다음 다섯가지가 있다.
- Object removeFirst() : 맨 앞 요소를 제거 (제거한 요소는 반환)
- Object remove() : 맨 앞 요소를 제거
- Object removeLast() : 맨 뒤 요소를 제거
- Object remove(int index) : 인덱스 위치의 요소를 제거
- boolean remove(Object value) : 요소값이 일치하는 위치의 요소를 제거 (중복 요소값이 있을 경우 맨앞의 요소가 제거)
remove 작동원리는 add 메커니즘의 반대로 생각해서 구현해주면 그리 어렵지 않다.
removeFirst 구현
public E removeFirst() {
// 1. 만약 삭제할 요소가 아무것도 없으면 에러
if (head == null) {
throw new NoSuchElementException();
}
// 2. 삭제될 첫번째 요소의 데이터를 백업
E value = head.item;
// 3. 두번째 노드를 임시 저장
Node<E> first = head.next;
// 4. 첫번째 노드의 내부 요소를 모두 삭제
head.next = null;
head.item = null;
// 5. 요소가 삭제 되었으니 크기 감소
size--;
// 6. head가 다음 노드를 가리키도록 업데이트
head = first;
if (first == null) {
// 7. 만일 리스트의 유일한 값을 삭제해서 빈 리스트가 될 경우, tail도 null 처리
tail = null;
} else {
// 8. 만일 빈 리스트가 아닐경우, 삭제되기 이전 두번째 이었던 first가 첫번째 노드가 되니 prev를 null 처리
first.prev = null;
}
// 9. 마지막으로 삭제된 요소를 반환
return value;
}
1. 반환할 삭제할 첫번째 요소 데이터를 백업한다.
2. 첫째 요소가 삭제가 되면 두번째 요소가 첫째가 되기 때문에 두번째 요소를 변수 first에 저장해서 나중에 다루도록 한다.
3. 추후에 cicular 처리를 위해 마지막 요소도 last에 저장해준다.
3. 첫번째 노드의 모든 데이터를 null로 처리한다.
4. head의 포인트를 first 변수에 저장해두었던 두번째 노드(@200)으로 업데이트한다.
5. 리스트의 첫번째 노드가 된 first의 노드 prev를 null로 업데이트한다.
6. 아무것도 연결되지 않아 고아가 되버린 노드는 나중에 GC가 수거해 간다.
+ 만일 삭제할 요소가 리스트의 유일한 요소라면, 삭제할시 빈 리스트가 되므로 head와 tail을 null이 되도록 업데이트 해준다.
remove 구현
LinkedList의 기본 remove() 동작은 add()와 달리 첫째 요소를 처리한다.
public E remove() {
return removeFirst();
}
removeLast 구현
public E removeLast() {
// 1. 만약 삭제할 요소가 아무것도 없으면 에러
if (tail == null) {
throw new NoSuchElementException();
}
// 2. 삭제될 마지막 요소의 데이터를 백업
E value = tail.item;
// 3. 마지막 노드의 이전 노드를 임시 저장
Node<E> last = tail.prev;
// 4. 마지막 노드의 내부 요소를 모두 삭제
tail.item = null;
tail.prev = null;
// 5. 요소가 삭제 되었으니 크기 감소
size--;
// 6. tail이 이전 노드를 가리키도록 업데이트
tail = last;
if(last == null) {
// 7. 만일 리스트의 유일한 값을 삭제해서 빈 리스트가 될 경우, head도 null 처리
head = null;
} else {
// 8. 만일 빈 리스트가 아닐경우, 삭제되기 이전 마지막의 이전 노드 이었던 last가 마지막 노드가 되니 next를 null 처리
last.next = null;
}
// 9. 마지막으로 삭제된 요소를 반환
return value;
}
1. 반환할 삭제할 마지막 요소 데이터를 백업한다.
2. 마지막 요소가 삭제가 되면 마지막 이전(@200) 노드가 마지막이 되기 때문에 마지막 이전 요소를 변수 last에 저장해서 나중에 다루도록 한다.
3. 마지막 노드의 모든 데이터를 null로 처리한다.
4. tail의 포인트를 last 변수에 저장해두었던 마지막 노드(@200)으로 업데이트한다.
5. 리스트의 마지막 노드가 된 last의 노드 next를 null로 업데이트한다.
6. 아무것도 연결되지 않아 고아가 되버린 노드는 나중에 GC가 수거해 간다.
+ 만일 삭제할 요소가 리스트의 유일한 요소라면, 삭제할시 빈 리스트가 되므로 head와 tail을 null이 되도록 업데이트 해준다.
인덱스로 remove 구현
public E remove(int index) {
// 1. 인덱스가 0보다 작거나 size 보다 크거나 같은 경우 에러 (size와 같을 경우 빈 공간을 가리키는 거니까)
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException();
}
// 2. 인덱스가 0이면 removeFirst 메서드 실행
if (index == 0) {
return removeFirst();
}
// 3. 인덱스가 size - 1(마지막 요소 위치) 이면 removeLast 메서드 실행
if (index == size - 1) {
return removeLast();
}
// 4. 삭제할 위치의 노드 저장
Node<E> del_node = search(index);
// 5. 삭제할 위치의 이전 노드 저장
Node<E> prev_node = del_node.prev;
// 6. 삭제할 위치의 다음 노드 저장
Node<E> next_node = del_node.next;
// 7. 삭제될 첫번째 요소의 데이터를 백업
E value = del_node.item;
// 8. 삭제 노드의 내부 요소를 모두 삭제
del_node.item = null;
del_node.prev = null;
del_node.next = null;
// 9. 요소가 삭제 되었으니 크기 감소
size--;
// 10. 이전 노드가 다음 노드를 가리키도록 업데이트
prev_node.next = next_node;
// 11. 다음 노드가 이전 노드를 가리키도록 업데이트
next_node.prev = prev_node;
// 12. 마지막으로 삭제된 요소를 반환
return value;
}
1. 삭제할 위치(index : 1)를 탐색한다.
2. search 메서드에서 @200 번지 노드를 반환하게 되는데 이를 이용하여, 삭제하려는 위치의 이전 노드(prev_node) 와 삭제 노드(del_node) 그리고 다음 노드(next_node) 참조값을 변수 3개에 저장한다.
3. 그리고 반환할 데이터를 백업해둔다.
4. del_node의 데이터를 모두 삭제한다.
5. prev_node의 next 값을 next_node로 재설정한다.
6. next_node의 prev 값을 next_node로 재설정한다.
7. 아무것도 연결되지 않아 고아가 되버린 노드는 나중에 GC가 수거해 간다.
+ 만일 삭제할 요소가 리스트의 유일한 요소라고 해도 상단에서 조건문으로 분기하기 때문에 신경쓸 필요가 없다.
값으로 remove 구현
값으로 요소를 remove 하는 로직은 인덱스로 요소를 remove 하는 로직과 다를바 없다.
다만 전체적인 로직은 거의 차이가 없지만 코드 구성 부분에서 차이가 난다. 왜냐하면 search() 메서드를 사용할수 없기 때문에 직접 순회를 하여야 하는데 이 과정이 약간 복잡할수도 있다.
public boolean remove(Object value) {
// 1. 삭제 노드를 저장할 변수 선언
Node<E> del_node = null;
// 2. 리스트를 루프할 변수 선언
Node<E> i = head;
// 3. 노드의 next를 순회하면서 해당 값을 찾는다.
while (i != null) {
// 노드의 값과 매개변수 값이 같으면
if (Objects.equals(i.item, value)) {
del_node = i; // 삭제 노드에 요소를 대입하고 break
break;
}
i = i.next;
}
// 4. 만일 찾은 요소가 없다면 false 리턴
if (del_node == null) {
return false;
}
// 5. 만약 삭제하려는 노드가 head(첫번째 요소) 라면, 기존 removeFirst()를 사용
if (del_node == head) {
removeFirst();
return true;
}
// 6. 만약 삭제하려는 노드가 last(마지막 요소) 라면, 기존 removeLast()를 사용
if (del_node == tail) {
removeLast();
return true;
}
// 7. 이전 노드, 다음 노드 구하기
Node<E> prev_node = del_node.prev;
Node<E> next_node = del_node.next;
// 8. 삭제 요소 데이터 모두 제거
del_node.item = null;
del_node.prev = null;
del_node.next = null;
// 9. 요소가 삭제 되었으니 크기 감소
size--;
// 10. 이전 노드와 다음 노드 끼리 서로 링크드 설정
prev_node.next = next_node;
next_node.prev = prev_node;
return true;
}get / set 구현하기
원소 get 동작은 위에서 구현한 search() 메서드로 노드를 검색하여 값을 반환하면 되고, 원소 set 동작은 마찬가지로 노드를 검색하고 노드의 값만 바꾸면 된다.
public E get(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException();
}
return search(index).item;
}public void set(int index, E value) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException();
}
// 1. search 메소드를 이용해 교체할 노드를 얻는다.
Node<E> replace_node = search(index);
// 2. 교체할 노드의 요소를 변경한다.
replace_node.item = null;
replace_node.item = value;
}indexOf 구현하기
리스트에서 해당 값이 들어있는 인덱스 위치를 얻는 메서드는 다음과 같다.
- indexOf(Object value) : 순차대로 검색해서 위치 반환
- lastindexOf(Object value) : 거꾸로 검색해서 위치 반환
만일 찾고자 하는 값이 배열에 중복으로 여러개 들어있으면, 가장 먼저 검색되는 요소의 위치를 반환한다. 그리고 만일 찾고자 하는 값이 없을 경우 -1 을 반환하도록 설정한다.
public int indexOf(Object value) {
Node<E> n = head;
int i = 0;
while(n != null) {
if(Objects.equals(value, n.item)) {
return i;
}
i++;
n = n.next;
}
return -1;
}public int lastIndexOf(Object value) {
Node<E> n = tail;
int i = size - 1;
while(n != null) {
if(Objects.equals(value, n.item)) {
return i;
}
i--;
n = n.prev;
}
return -1;
}기타 요소 구현하기
size 구현
MyLinkedList 클래스에서는 size 변수가 private 접근제한자를 갖기 때문에 만일 외부에서 참조가 필요하다면 메서드를 통해 반환하는 식으로 처리해야 한다. 만일 size 변수가 pubilc이라면 외부에서 고의적으로 size값을 바꿔버리면 MyLinkedList 동작 자체가 이상해버릴수 있기 때문이다.
public int size() {
return size;
}
isEmpty 구현
리스트가 비어있는지 아닌지 확인하려면 아주 간단하게 요소의 갯수인 size 변수값이 0인지만 확인하면 된다.
public boolean isEmpty() {
return size == 0;
}
clear 구현
모든 요소들을 지우기 위해 반복문으로 리스트 전체를 순회하여 각 노드에 null을 대입하는 식으로 구성한다.
public void clear() {
// i.next가 null이 면 마지막을 의미하는거니, null 이 아닐때 까지 순회
for(Node<E> i = head; i.next != null;) {
Node<E> next_node = i.next; // i에 관한 모든 값을 지울 것이기 때문에 미리 백업한다.
i.item = null;
i.prev = null;
i.next = null;
i = next_node;
}
head = null;
tail = null;
size = 0; // 모든 요소를 지웠으니 size도 초기화
}
contains 구현
indexOf() 메소드는 사용자가 찾고자 하는 요소(value)의 위치를 반환하는 메소드였다면, contains() 메서드는 사용자가 찾고자 하는 요소가 존재 하는지 안하는지를 true / false 를 반환하는 메소드다. 이 역시 기존의 indexOf() 메서드를 재활용하여 매우 간단하게 구현할 수 있다.
public boolean contains(Object value) {
return indexOf(value) != -1; // -1 이 아니라는 말은 요소가 리스트에 존재한다는 것이다.
}
toString 구현
마지막으로 링크드 리스트 요소들을 출력하기 위해 Object 클래스의 toString() 메소드를 오버라이딩 하자.
연결 리스트 출력은 어렵게 생각할 필요 없이, 배열을 만들고 각 배열 인덱스 마다 리스트의 노드 요소값을 대입해 복사를 한뒤 문자열로 만들어 반환해주면 된다.
@Override
public String toString() {
// 1. 만일 head 가 null 일 경우 빈 배열
if(head == null) {
return "[]";
}
// 2. 현재 size만큼 배열 생성
Object[] array = new Object[size];
// 3. 노드 next를 순회하면서 배열에 노드값을 저장
int index = 0;
Node<E> n = head;
while (n != null) {
array[index] = (E) n.item;
index++;
n = n.next;
}
// 3. 배열을 스트링화하여 반환
return Arrays.toString(array);
}아니면 다음과 같이 직접 문자열 더하기 연산으로도 구현해도 문제는 없다.
@Override
public String toString() {
if(head == null) {
return "[]";
}
Node<E> n = head;
String result = "[";
while(n.next != null) {
result += n.item + ", ";
n = n.next;
}
// n이 마지막일 경우 n.next가 null이니 루프문을 빠져나오게 되서 마지막 노드 삽입 처리를 해주어야 한다.
result += n.item + "]";
return result;
}LinkedList 커스텀 toString
기존 toString 처럼 단순히 배열 문자열을 콘솔에 출력하는 것이 아닌, 각 노드의 링크드 주소와 함께 연결 리스트의 전체 참조 요소들을 출력해주는 커스텀 toString() 메서드를 만들어 보았다.
왼쪽은 해당 리스트 원소 노드의 주소 해시값이며, [이전 노드 주소 | 노드 아이템값 | 다음 노드 주소] 식으로 요소를 출력한다. 만일 독자분들이 구축한 메서드가 정말로 링크 연결이 잘 동작되는지 확인해보고 싶다면 이 커스텀 메서드를 통해 한눈에 노드 참조를 확인할 수 있을 것이다.
public String toString2() {
if (head == null) {
return "[]";
}
Node<E> n = head;
StringBuilder result = new StringBuilder();
result.append("[\n");
for(int i = 0; i< size; i++) {
result.append(" Node@").append(String.format("%-10s", n.hashCode())).append(" → ");
if (n.prev != null) {
result.append("[").append(n.prev.hashCode()).append(" | ");
} else {
result.append("[").append("null").append(" | ");
}
result.append(n.item).append(" | ");
if (n.next != null) {
result.append(n.next.hashCode()).append("]");
} else {
result.append("null").append("]");
}
result.append(", \n");
n = n.next;
}
result.append("]");
return result.toString();
}public static void main(String[] args) {
MyDoublyLinkedList<Number> list = new MyDoublyLinkedList<>();
list.addLast(2);
list.addFirst(1);
list.addLast(3);
list.add(2, 2.5);
System.out.println(list.toString2());
}
Doubly LinkedList 구현 전체 코드
public class MyDoublyLinkedList<E> {
private Node<E> head; // 노드의 첫 부분을 가리키는 레퍼런스
private Node<E> tail; // 노드의 끝 부분을 가리키는 레퍼런스
private int size; // 리스트 요소 갯수
// 생성자
public MyDoublyLinkedList() {
this.head = null;
this.tail = null;
this.size = 0;
}
// inner static class
private static class Node<E> {
private E item; // Node에 담을 데이터
private Node<E> next; // 다음 Node 객체를 가르키는 래퍼런스
private Node<E> prev; // 이전 Node 객체를 가르키는 래퍼런스
// 생성자 (이전 노드 포인트 | 데이터 | 다음 노드 포인트)
Node(Node<E> prev, E item, Node<E> next) {
this.item = item;
this.next = next;
this.prev = prev;
}
}
private Node<E> search(int index) {
Node<E> n; // 반환할 노드
if ((size / 2) > index) {
// 1. 만일 인덱스가 시작에 가까우면, 순차 탐색
n = head;
for (int i = 0; i < index; i++) {
n = n.next;
}
} else {
// 2. 만일 인덱스가 끝에 가까우면, 역순 탐색
n = tail;
for (int i = size - 1; i > index; i--) {
n = n.prev;
}
}
return n;
}
public void addFirst(E value) {
// 1. head를 임시 백업함
Node<E> first = head;
// 2. 새 노드를 추가 (이때 첫번째 노드니까 prev는 null이 되고 next는 head가 가리키는 노드가 되게 된다)
Node<E> new_node = new Node<>(null, value, first);
// 3. 노드를 추가하였으니 리스트 크기 증가
size++;
// 4. 첫번째 기준이 변경되었으니 head를 삽입된 새 노드로 참조하도록 업데이트
head = new_node;
if (first == null) {
// 5. 만일 빈 리스트에서 최초의 요소 추가였을 경우, tail도 첫째 노드를 바라보도록 업데이트
tail = new_node;
} else {
// 6. 만일 빈 리스트가 아닐경우, 추가되기 이전 첫번째이었던 노드에서 prev를 새 노드로 참조하도록 업데이트
first.prev = new_node;
}
}
public void addLast(E value) {
// 1. tail를 임시 백업함
Node<E> last = tail;
// 2. 새 노드를 추가 (이때 마지막 노드니까 next는 null이 되고 prev는 tail이 가리키는 노드가 되게 된다)
Node<E> new_node = new Node<>(last, value, null);
// 3. 노드를 추가하였으니 리스트 크기 증가
size++;
// 4. 마지막 기준이 변경되었으니 tail를 삽입된 새 노드로 참조하도록 업데이트
tail = new_node;
if (last == null) {
// 5. 만일 빈 리스트에서 최초의 요소 추가였을 경우, head도 첫째 노드를 바라보도록 업데이트
head = new_node;
} else {
// 6. 만일 빈 리스트가 아닐경우, 추가되기 이전 마지막이었던 노드에서 next를 새 노드로 참조하도록 업데이트
last.next = new_node;
}
}
public boolean add(E value) {
addLast(value);
return true;
}
public void add(int index, E value) {
// 1. 인덱스 범위 체크
// 인덱스가 0보다 작거나 size 보다 클 경우 에러
// (인덱스가 size보다 크면 마지막 요소 다음 빈공간의 다음 빈공간을 가리키는 거니까)
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
}
// 2. 추가하려는 index가 0이면 addFirst 호출
if (index == 0) {
addFirst(value);
return;
}
// 3. 추가하려는 index가 size와 같으면 addLast 호출
if (index == size) {
addLast(value);
return;
}
// 4. 추가하려는 위치의 다음 노드 얻기
Node<E> next_node = search(index);
// 5. 추가하려는 위치의 이전 노드 얻기
Node<E> prev_node = next_node.prev;
// 6. 새 노드 생성 (바로 이전 / 다음 노드와 연결됨)
Node<E> new_node = new Node<>(prev_node, value, next_node);
// 7. 노드를 추가하였으니 리스트 크기 증가
size++;
// 8. 이전 노드의 next를 새 노드에 연결
prev_node.next = new_node;
// 9. 다음 노드의 prev를 새 노드에 연결
next_node.prev = new_node;
}
public E removeFirst() {
// 1. 만약 삭제할 요소가 아무것도 없으면 에러
if (head == null) {
throw new NoSuchElementException();
}
// 2. 삭제될 첫번째 요소의 데이터를 백업
E value = head.item;
// 3. 두번째 노드를 임시 저장
Node<E> first = head.next;
// 4. 첫번째 노드의 내부 요소를 모두 삭제
head.next = null;
head.item = null;
// 5. 요소가 삭제 되었으니 크기 감소
size--;
// 6. head가 다음 노드를 가리키도록 업데이트
head = first;
if (first == null) {
// 7. 만일 리스트의 유일한 값을 삭제해서 빈 리스트가 될 경우, tail도 null 처리
tail = null;
} else {
// 8. 만일 빈 리스트가 아닐경우, 삭제되기 이전 두번째 이었던 first가 첫번째 노드가 되니 prev를 null 처리
first.prev = null;
}
// 9. 마지막으로 삭제된 요소를 반환
return value;
}
public E remove() {
return removeFirst();
}
public E removeLast() {
// 1. 만약 삭제할 요소가 아무것도 없으면 에러
if (tail == null) {
throw new NoSuchElementException();
}
// 2. 삭제될 첫번째 요소의 데이터를 백업
E value = tail.item;
// 3. 마지막 노드의 이전 노드를 임시 저장
Node<E> last = tail.prev;
// 4. 마지막 노드의 내부 요소를 모두 삭제
tail.item = null;
tail.prev = null;
// 5. 요소가 삭제 되었으니 크기 감소
size--;
// 6. tail이 이전 노드를 가리키도록 업데이트
tail = last;
if (last == null) {
// 7. 만일 리스트의 유일한 값을 삭제해서 빈 리스트가 될 경우, head도 null 처리
head = null;
} else {
// 8. 만일 빈 리스트가 아닐경우, 삭제되기 이전 마지막의 이전 노드 이었던 last가 마지막 노드가 되니 next를 null 처리
last.next = null;
}
// 9. 마지막으로 삭제된 요소를 반환
return value;
}
public E remove(int index) {
// 1. 인덱스가 0보다 작거나 size 보다 크거나 같은 경우 에러 (size와 같을 경우 빈 공간을 가리키는 거니까)
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException();
}
// 2. 인덱스가 0이면 removeFirst 메서드 실행
if (index == 0) {
return removeFirst();
}
// 3. 인덱스가 size - 1(마지막 요소 위치) 이면 removeLast 메서드 실행
if (index == size - 1) {
return removeLast();
}
// 4. 삭제할 위치의 노드 저장
Node<E> del_node = search(index);
// 5. 삭제할 위치의 이전 노드 저장
Node<E> prev_node = del_node.prev;
// 6. 삭제할 위치의 다음 노드 저장
Node<E> next_node = del_node.next;
// 7. 삭제될 첫번째 요소의 데이터를 백업
E value = del_node.item;
// 8. 삭제 노드의 내부 요소를 모두 삭제
del_node.item = null;
del_node.prev = null;
del_node.next = null;
// 9. 요소가 삭제 되었으니 크기 감소
size--;
// 10. 이전 노드가 다음 노드를 가리키도록 업데이트
prev_node.next = next_node;
// 11. 다음 노드가 이전 노드를 가리키도록 업데이트
next_node.prev = prev_node;
// 12. 마지막으로 삭제된 요소를 반환
return value;
}
public boolean remove(Object value) {
// 1. 삭제 노드를 저장할 변수 선언
Node<E> del_node = null;
// 2. 리스트를 루프할 변수 선언
Node<E> i = head;
// 3. 노드의 next를 순회하면서 해당 값을 찾는다.
while (i != null) {
// 노드의 값과 매개변수 값이 같으면
if (Objects.equals(i.item, value)) {
del_node = i; // 삭제 노드에 요소를 대입하고 break
break;
}
i = i.next;
}
// 4. 만일 찾은 요소가 없다면 false 리턴
if (del_node == null) {
return false;
}
// 5. 만약 삭제하려는 노드가 head(첫번째 요소) 라면, 기존 removeFirst()를 사용
if (del_node == head) {
removeFirst();
return true;
}
// 6. 만약 삭제하려는 노드가 last(마지막 요소) 라면, 기존 removeLast()를 사용
if (del_node == tail) {
removeLast();
return true;
}
// 7. 이전 노드, 다음 노드 구하기
Node<E> prev_node = del_node.prev;
Node<E> next_node = del_node.next;
// 8. 삭제 요소 데이터 모두 제거
del_node.item = null;
del_node.prev = null;
del_node.next = null;
// 9. 요소가 삭제 되었으니 크기 감소
size--;
// 10. 이전 노드와 다음 노드 끼리 서로 링크드 설정
prev_node.next = next_node;
next_node.prev = prev_node;
return true;
}
public E get(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException();
}
return search(index).item;
}
public void set(int index, E value) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException();
}
// 1. search 메소드를 이용해 교체할 노드를 얻는다.
Node<E> replace_node = search(index);
// 2. 교체할 노드의 요소를 변경한다.
replace_node.item = null;
replace_node.item = value;
}
public int indexOf(Object value) {
Node<E> n = head;
int i = 0;
while (n != null) {
if (Objects.equals(value, n.item)) {
return i;
}
i++;
n = n.next;
}
return -1;
}
public int lastIndexOf(Object value) {
Node<E> n = tail;
int i = size - 1;
while (n != null) {
if (Objects.equals(value, n.item)) {
return i;
}
i--;
n = n.prev;
}
return -1;
}
public int size() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
public void clear() {
// i.next가 null이 면 마지막을 의미하는거니, null 이 아닐때 까지 순회
for (Node<E> i = head; i.next != null; ) {
Node<E> next_node = i.next; // i에 관한 모든 값을 지울 것이기 때문에 미리 백업한다.
i.item = null;
i.prev = null;
i.next = null;
i = next_node;
}
head = null;
tail = null;
size = 0; // 모든 요소를 지웠으니 size도 초기화
}
public boolean contains(Object value) {
return indexOf(value) != -1; // -1 이 아니라는 말은 요소가 리스트에 존재한다는 것이다.
}
@Override
public String toString() {
if (head == null) {
return "[]";
}
Node<E> n = head;
String result = "[";
while (n.next != null) {
result += n.item + ", ";
n = n.next;
}
// n이 마지막일 경우 n.next가 null이니 루프문을 빠져나오게 되서 마지막 노드 삽입 처리를 해주어야 한다.
result += n.item + "]";
return result;
}
public String toString2() {
if (head == null) {
return "[]";
}
Node<E> n = head;
StringBuilder result = new StringBuilder();
result.append("[\n");
for (int i = 0; i < size; i++) {
result.append(" Node@").append(String.format("%-10s", n.hashCode())).append(" → ");
if (n.prev != null) {
result.append("[").append(n.prev.hashCode()).append(" | ");
} else {
result.append("[").append("null").append(" | ");
}
result.append(n.item).append(" | ");
if (n.next != null) {
result.append(n.next.hashCode()).append("]");
} else {
result.append("null").append("]");
}
result.append(", \n");
n = n.next;
}
result.append("]");
return result.toString();
}
}마지막으로 내가 직접 짠 자료구조 클래스가 정상적으로 예외 없이 동작하는지 데이터 테스트를 잊지말자!
public static void main(String[] args) {
MyDoublyLinkedList<Number> list = new MyDoublyLinkedList<>();
list.addFirst(1);
list.addLast(2);
list.addLast(3);
list.addLast(4);
list.addLast(5);
System.out.println(list.toString2());
list.removeFirst();
System.out.println(list.toString2());
list.removeLast();
System.out.println(list.toString2());
list.remove(2.5);
System.out.println(list.toString2());
System.out.println(list.get(2));
list.set(1, 3.5);
System.out.println(list.toString2());
}
# 참고자료
https://www.alphacodingskills.com/ds/doubly-linked-list.php
https://youtu.be/-dr28wmorIM
이 글이 좋으셨다면 구독 & 좋아요
여러분의 구독과 좋아요는
저자에게 큰 힘이 됩니다.
