✅바로 가기
- Doubly Linked List 서론
- 리스트 인터페이스
- 노드 클래스
- 리스트 생성자와 필드, 내부 클래스
- search(int index)
- add()
- remove()
- isEmpty(), isFull(), get(int index), set(int index, E element)
- indexOf(E element), contains(E element)
- size(), capacity(), toArray()
- 전체코드
Doubly Linked List는 노드가 앞 뒤를 가리키는 링크가 존재하는 구조이다. Singly Linked List와 달리 노드가 앞 뒤 노드를 가리키고 있는 구조인 것이다.
Doubly Linked List의 장점은?
각 노드가 다음(next)과 이전 (prev) 노드 모두 가리키는 구조이다.
노드의 앞 뒤 노드를 가리키는 구조이므로 양방향 순회가 가능하다.
노드의 삭제 연산이 Singly Linked List보다 더 빠르다.
양쪽으로 삽입과 삭제가 가능해진다.
Deque 구현에 매우 적합하다.
🔍 구조 비교
| 항목 | Singly Linked | Doubly Linked List |
| 포인터 수 | 1개 (next) | 2개 (prev, next) |
| 메모리 사용량 | 적음 | 더 많음 |
| 오버해드 | 보다 적다 | 많다 |
| 노드 추가 삭제 복잡도 | 제한적으로 | 보다 유연하다 |
| 양방향 순회 | 불가능 | 가능 |
| 구현 복잡도 | 간단하다 | 약간 더 복잡하다. |
✨ 리스트 인터페이스
Singly Linked List와 ArrayList 구현했을 때 사용했던 List 인터페이스이다.
package list;
public interface ListI<E> {
/**
* List 맨 앞에 요소를 추가합니다. (append)
*
* @param element 새롭게 추가되는 값
*/
public void addFirst(E element);
/**
* List 특정 index에 요소를 추가합니다.
*
* @param index 특정 index에 접근하는 변수
* @param element 특정 index에 넣을 값
*/
public void add(int index, E element);
/**
* List에 요소 추가 기본적으로 append 맨 뒤에 추가.
*
* @param element list에 삽입할 값
*/
public void add(E element);
/**
* List 맨 마지막에 요소를 추가합니다.
*
* @param element 새롭게 추가되는 값
*/
public void addLast(E element);
/**
* 특정 요소가 몇 번째 index에 존재하는지 반환하는 메서드
*
* @param element 찾고자 하는 값
* @return 찾았을 때 index값 반환
* 없다면 -1 반환
*/
public int indexOf(E element);
/**
* 특정 index에 요소 제거
*
* @param index 제거하고자 하는 특정 index값
* @return 제거한 값 반환
*/
public E remove(int index);
/**
*
*/
public E remove(E element);
/**
* 리스트가 공백 상태인지 확인하는 메서드
*
* @return 공백일 시 true 공백이 아닐 시 false
*/
public boolean isEmpty();
/**
* 리스트가 포화 상태인지 확인하는 메서드
*
* @return 포화일 시 true 포화가 아닐 시 false
*/
public boolean isFull();
/**
* 특정 index의 요소 반환
*
* @param index 찾을 위치 index
* @return 찾은 요소 반환
*/
public E get(int index);
/**
* 특정 index의 요소를 매개변수 요소로 변경하는 메서드
*
* @param index 바꿀려는 index 위치 값
* @param element 바뀌어지는 값
*/
public void set(int index, E element);
/**
* @param element
* @return element값이 리스트에 존재하면 true 아니면 false
*/
public boolean contains(E element);
/**
* 리스트에 존재하는 요소의 개수 반환
*
* @return 리스트의 총 용량
*/
public int size();
/**
* 리스트의 총 용량 반환.
*
* @return 리스트의 총 용량
*/
public int capacity();
}
✨ 노드 클래스
이번에는 내부 클래스로 구현하였다.
Singly Liked List와 다른 점은 prev 변수가 새로 생겼다.
/**
* 내부정의 클래스
*
* @param <E>
*/
private static class Node<E> {
E data;
Node<E> link;
Node<E> prev;
Node(E data) {
this.data = data;
}
}
✨ 리스트 생성자와 필드, 내부 클래스
import list.ListI;
import java.util.NoSuchElementException;
//Doubly Linked List 구현
//맴버변수: size, head, tail
public class DoublyLinkedList<E> implements ListI<E> {
private int size; //리스트의 총 노드의 개수
private Node<E> head; //리스트의 맨 앞 노드를 가리키는 변수
private Node<E> tail; //리스트의 맨 뒤의 노드를 가리키는 변수
DoublyLinkedList() {
head = null;
tail = null;
size = 0;
}
/**
* 내부정의 클래스
*
* @param <E>
*/
private static class Node<E> {
E data;
Node<E> link;
Node<E> prev;
Node(E data) {
this.data = data;
}
}
✨ search(int index)
링크드 리스트는 index라는 개념이 존재하지 않지만 접근성과 이해력을 높이기 위해 index라는 가상으로 접근하는 방식이다.
배열처럼 index로 표현하면 더 이해하기 쉽기 때문이다.
prev 변수도 존재하므로 양방향 접근성을 살릴 수 있게 구현하였다.
리스트의 총 노드의 개수를 2로 나누었을 때 parameter index 값보다 작다면 리스트가 후단부의 노드를 탐색하는 것이므로 tail부터 탐색한다.
! 진짜 index가 아니라는 점
/**
* parameter로 받은 특정 index값으로 리스트의 특정 노드를 반환하는 메서드이다.
* 여기서 linked list는 index라는 개념은 존재하지 않지만, 노드의 생성 순서에 맞게 가상의 index를 부여한다.
*
* @param index 찾고자하는 특정 index값
* @return 노드 탐색을 성공했으면 탐색한 노드를 반환한다.
* @throws IndexOutOfBoundsException index가 음수이거나 리스트의 크기보다 같거나 크다면 예외발생
*/
public Node<E> search(int index) throws IndexOutOfBoundsException {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException();
}
if (index + 1 > size / 2) {
Node<E> searchNode = tail;
for (int i = size - 1; i > index; i--) {
searchNode = searchNode.prev;
}
return searchNode;
} else {
Node<E> searchNode = head;
for (int i = 0; i < index; i++) {
searchNode = searchNode.link;
}
return searchNode;
}
}
✨ add(E element)
리스트에 노드를 추가하는 기능이다.
추가하는 방식은 총 4가지이다.
1. addFirst(E element)
2. add(int index, E element)
3. add(E element)
4. addLast(E element)
1. addFirst(E element)
리스트의 전단부에 노드를 삽입하는 연산이다.
addFirst의 로직은 다음과 같다.
1. 추가할 노드 생성
2. 노드의 링크를 head와 연결한다. 만약 head가 null이면 새로운 노드의 링크값은 null일 것이다.
3. head를 새로운 노드로 변경한다. head는 이로 인해 리스트의 전단부 노드만 가리키게 할 수 있다.
4. size==0 이면 리스트에 노드가 하나도 없는 상태이므로 tail도 새로운 노드 주소를 대입한다.
5. size 값 업데이트.
2. add(int index, E element)
add(int index E element)는 리스트에 특정 위치에 노드를 삽입한다.
특정 위치는 index로 가정한다.
로직
1. 매개변수 index가 0보다 적가나 size보다 크다면 예외를 발생시킨다.
2. index==0일 시 addFirst를 호출한다.
3. index==size 일 시 addLast를 호출한다.
4. 매개변수 index 기준 index-1 노드를 찾는다. 찾은 노드를 prevNode 포인터 변수에 대입한다.
5. index-1 노드의 link 값을 nextNode에 대입한다.
6. 새로운 노드를 생성한다.
7. prevNode 링크를 새로운 노드와 연결하고 nextNode의 prev를 새로운 노드와 연결한다.
8. 새로운 노드의 prev를 prevNode 새로운 노드의 link를 nextNode와 연결한다.
9. size값을 업데이트한다.
3. add(E element)
Java에서 제공하는 링크드리스트도 add의 기본 로직이 addLast처럼 리스트 맨 뒤에 추가하는 방식이다.
로직
1. addLast 호출
4. addLast(E element)
로직
1. 새로운 노드 생성
2. 만약 tail이 null이라면 리스트가 빈 상태이므로 head = tail = newNode
3. null이 아니라면 새로운 노드의 prev를 tail과 연결한다. tail의 링크를 새로운 노드, tail을 새로운 노드로 대입한다.
4. size값 업데이트
add 전체 코드
/**
* 리스트의 전단부 맨 앞에 노드를 추가한다.
*
* @param element 새롭게 추가되는 값
*/
@Override
public void addFirst(E element) {
Node<E> newNode = new Node<E>(element);
newNode.link = head;
if (newNode.link != null) {
head.prev = newNode;
}
head = newNode;
if (size == 0) {
tail = newNode;
}
size++;
}
/**
* 리스트의 특정 index 부분에 노드를 추가한다.
* 핵심은 이전노드와 이전노드의 link노드를 새로 추가하고자 하는 노드와
* 잘 연결 시켜야한다.
*
* @param index 특정 index에 접근하는 변수
* @param element 특정 index에 넣을 값
* @throws IndexOutOfBoundsException index가 음수이거나 리스트의 크기보다 크면 예외 발생
*/
@Override
public void add(int index, E element) throws IndexOutOfBoundsException {
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException();
}
if (index == 0) {
addFirst(element);
return;
}
if (index == size) {
addLast(element);
return;
}
Node<E> prevNode = search(index - 1);
Node<E> nextNode = prevNode.link;
Node<E> newNode = new Node<E>(element);
prevNode.link = newNode;
nextNode.prev = newNode;
newNode.prev = prevNode;
newNode.link = nextNode;
size++;
}
/**
* Java에서 제공하는 링크드리스트도 add의 기본은 addLast이다.
*
* @param element list에 삽입할 값
*/
@Override
public void add(E element) {
addLast(element);
}
@Override
public void addLast(E element) {
Node<E> newNode = new Node<>(element);
if (tail == null) {
head = tail = newNode;
} else {
newNode.prev = tail;
tail.link = newNode;
tail = newNode;
}
size++;
}
✨remove
리스트의 노드를 삭제하는 기능이다.
리스트의 삭제 방식은 리스트의 위치 index를 기준으로 삭제하는 방법, 특정 값을 가진 노드를 삭제하는 방법, 리스트의 맨 앞 노드를 삭제하는 방법 3가지로 구현하였다.
1.remove(int index)
2.remove(E element)
3.remove()
1. remove(int index)
리스트의 특정 위치 (index)에 해당하는 노드를 삭제하는 기능이다.
로직
1. index<0 || index>= size 이면 매개변수로 들어온 인덱스 값이 리스트에는 존재하지 않으니 예외를 발생시킨다.
2. index==0 이면 리스트의 맨 앞 노드를 삭제하는 기능인 remove()를 호출한다.
3. 삭제할 노드를 search로 찾고 찾은 노드의 prev 노드 next 노드를 가져온다.
4. 삭제할 노드의 데이터 필드값을 미리 변수에 저장한다.
5. 삭제할 노드의 링크가 null이면 삭제할 노드가 tail이므로 prevNode 링크를 널로 바꾸고 tail에 prevNode를 삽입한다. 즉, prevNode가 tail 후단부 노드가 된다는 소리이다.
6. 삭제할 노드의 링크가 null이 아니라면 삭제할 노드 바로 뒤에 다른 노드가 존재하는 것이므로 prevNode 링크를 nextNode에 연결한다. nextNode의 prev를 prevNode와 연결한다.
7. 삭제할 노드의 데이터, 링크, 이전 노드를 모두 null로 변경하여 GC가 삭제하게끔 유도한다.
8. size값을 업데이트한다.
2. remove(E element)
리스트에 존재하는 노드들 중 특정 값을 가진 노드를 삭제하는 기능이다.
로직
1. 우선 리스트가 빈 상태인지 체크한다. 리스트가 공백 상태이면 예외를 발생시킨다.
2. head가 가리키는 노드부터 반복문을 돌려 인수로 전달받은 값과 동일한 노드를 찾는다.
3. 반복문을 돌려도 인수와 동일한 값을 가진 노드가 존재하지 않는다면 예외를 발생시킨다.
4. 반복문으로 찾은 결과 찾은 노드가 head와 동일하면 리스트의 맨 앞 노드를 삭제하는 remove() 메서드를 호출한다.
5. 삭제할 노드의 링크 노드와 이전 노드를 따로 저장한다.
6. 링크 노드가 null이라면 삭제할 노드가 tail이므로 tail을 prevNode로 변경한다.
7. 링크 노드가 null이 아니라면 prevNode의 링크를 nextNode로 nextNode의 이전 링크를 prevNode로 연결시켜 준다.
8. 삭제할 노드의 멤버들을 모두 null로 초기화하여 GC 자동 삭제를 유도한다.
9. size값 업데이트와 삭제 노드 값을 반환한다.
3. remove()
리스트의 맨 앞 노드를 삭제한다.
로직
1. head==null이라면 리스트가 공백 상태이므로 예외 발생시킨다.
2. 삭제할 노드가 head가 가리키는 노드이므로 head 노드의 데이터를 미리 변수에 저장한다.
3. head 노드의 link 노드를 참조변수 removeNextNode에 대입한다.
4. head 노드의 link 노드가 null이라면 head 삭제하는 기준으로 리스트가 공백 상태가 되므로 tail과 head를 모두 null로 변경한다.
5. null이 아니라면 head의 link 노드 prev 이전 노드가 head와 연결되어 있으므로 연결을 끊는다. head는 삭제될 노드이므로 head를 link노드로 변경한다.
6. head가 가리키는 노드를 모두 null로 변경하여 삭제 유도한다. size 값과 head 노드의 데이터 필드 값도 반환한다.
remove() 전체 코드
/**
* 특정 index에 존재하는 노드를 삭제한다.
* index 0 노드를 삭제하고자 하면 remove()를 호출한다.
*
* @param index 제거하고자 하는 특정 index값
* @return 삭제한 노드의 data 필드값을 반환한다.
* @throws IndexOutOfBoundsException index가 음수이거나 리스트의 크기보다 같거나 크면 예외 발생
*/
@Override
public E remove(int index) throws IndexOutOfBoundsException {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException();
}
if (index == 0) {
return remove();
}
Node<E> removeNode = search(index);
Node<E> prevNode = removeNode.prev;
Node<E> nextNode = removeNode.link;
E data = removeNode.data;
if (nextNode == null) {
prevNode.link = null;
tail = prevNode;
} else {
prevNode.link = nextNode;
nextNode.prev = prevNode;
}
removeNode.data = null;
removeNode.link = null;
removeNode.prev = null;
size--;
return data;
}
/**
* 특정 데이터값을 가진 노드를 삭제한다.
* 탐색한 노드가 head가 가리키는 노드라면 remove()를 호출한다.
*
* @param element 매개변수 값과 동일한 노드를 삭제한다.
* @return 삭제한 노드의 데이터 필드 값
* @throws NoSuchElementException size가 0이면 리스트가 빈 상태이므로 예외 발생
*/
@Override
public E remove(E element) throws NoSuchElementException {
if (isEmpty()) {
throw new NoSuchElementException();
}
Node<E> removeNode = head;
while (removeNode != null && !removeNode.data.equals(element)) {
removeNode = removeNode.link;
}
if (removeNode == null) {
throw new NoSuchElementException();
}
if (removeNode.equals(head)) {
return remove();
}
Node<E> nextNode = removeNode.link;
Node<E> prevNode = removeNode.prev;
if (nextNode == null) {
tail = prevNode;
prevNode.link = null;
} else {
prevNode.link = nextNode;
nextNode.prev = prevNode;
}
E returnData = removeNode.data;
removeNode.data = null;
removeNode.prev = null;
removeNode.link = null;
size--;
return returnData;
}
/**
* 리스트의 전단부 맨 앞 노드를 삭제한다.
* head가 가리키는 노드를 삭제
*
* @return 삭제한 노드의 데이터 필드 값
* @throws NoSuchElementException haed가 null이면 리스트가 빈 상태이므로 예외 발생
*/
public E remove() throws NoSuchElementException {
if (head == null) {
throw new NoSuchElementException("리스트가 빈 상태");
}
Node<E> removeNode = head;
E data = removeNode.data;
Node<E> removeNextNode = removeNode.link;
if (removeNextNode == null) {
tail = null;
head = null;
} else {
removeNextNode.prev = null;
head = removeNextNode;
}
removeNode.data = null;
removeNode.link = null;
removeNode.prev = null;
size--;
return data;
}
✨ isEmpty(), isFull(), get(int index), set(int index, E element)
1. isEmpty(), isFull()
두 메서드는 리스트의 공백과 포화 상태를 확인하는 기능이다.
연결 리스트는 동적 할당이므로 유연하게 크기를 조절할 수 있다. 따라서 Doulby Linked List는 포화 상태가 존재하지 않는다고 가정한다. 메모리 누수가 발생하면 포화상태이다.
/**
* 공백상태는 리스트의 노드의 개수를 기록하는 size변수를 이용한다.
*
* @return size가 0이거나 0보다 작은 음수이면 true 반환
*/
@Override
public boolean isEmpty() {
return size <= 0;
}
/**
* 동적구조이므로 메모리 누수가 아닌이상 포화상태 존재하지 않는다.
*
* @return false 기본값
*/
@Override
public boolean isFull() {
System.out.println("링크드 리스트 포화상태 없다고 가정: " + Integer.MAX_VALUE);
return false;
}
2. get(int index), set(int index, E element)
get(int index)는 리스트의 특정 위치의 노드를 반환하는 메서드이다.
set(int index, E element)는 리스트의 특정 위치의 노드의 데이터 필드 값을 변경하는 메서드이다.
/**
* 특정 노드의 데이터필드값 반환
*
* @param index 찾을 위치 index
* @return 데이터값
*/
@Override
public E get(int index) {
return search(index).data;
}
/**
* 특정 index의 노드의 E data 맴버변수 값을 변경한다.
*
* @param index 바꿀려는 index 위치 값
* @param element 바뀌어지는 값
*/
@Override
public void set(int index, E element) {
Node<E> node = search(index);
E outputData = node.data;
node.data = element;
System.out.println("기존 값: " + outputData + " 변경된 값: " + node.data);
}
✨ indexOf(E element), contains(E element)
indexOf, contains 메서드는 리스트가 검색 기능으로 indexOf는 찾은 노드의 위치값(index)을 반환하는 메서드이고 contains는 찾은 노드의 데이터 필드 값을 반환한다.
두 메서드는 노드의 데이터 필드 값을 비교하여 탐색한다.
/**
* 특정 값을 찾으면 index값을 반환해주는 메서드
*
* @param element 찾고자 하는 값
* @return 찾았을 경우 index 값 반환 없다면 -1반환
*/
@Override
public int indexOf(E element) throws NoSuchElementException {
Node<E> node = head;
if (size == 0) {
throw new NoSuchElementException();
}
for (int i = 0; i < size; i++, node = node.link) {
if (node.data.equals(element)) {
return i;
}
}
return -1;
}
/**
* 특정 data값을 지닌 노드가 존재하면 true 존재하지 않으면 false 반환
*
* @param element 찾고자하는 데이터 값
* @return 탐색 성공 시 true 실패 시 false
* @throws NoSuchElementException head가 null이면 검색할 노드가 존재하지 않으므로 예외발생
*/
@Override
public boolean contains(E element) throws NoSuchElementException {
if (head == null) {
throw new NoSuchElementException();
}
Node<E> node = head;
while (node != null) {
if (node.data.equals(element)) {
return true;
}
node = node.link;
}
return false;
}
✨ size(), capacity (), toArray()
size(): 리스트에 존재하는 노드의 총개수를 반환
capacity(): 리스트가 가질 수 있는 최대 크기를 반환 고정된 크기가 아니므로 Integer의 MAX_VALUE를 반환한다.
toArray(): 리스트에 존재하는 노드의 현재 상황을 배열형식으로 콘솔에 출력하는 메서드이다.
/**
* size값 반환
*
* @return
*/
@Override
public int size() {
return size;
}
/**
* 리스트의 최대 크기 반환
* 동적구조이므로 int 타입의 최대값 반환
*
* @return
*/
@Override
public int capacity() {
return Integer.MAX_VALUE;
}
/**
* 리스트에 존재하는 노드의 상황을 전단부부터 후단부까지 배열형식으로 출력한다.
*/
public void toArray() {
if (size == 0) {
System.out.println("[]");
return;
}
StringBuilder sb = new StringBuilder("[");
Node<E> node = head;
for (int i = 0; i < size; i++) {
if (i != size - 1) {
sb.append(node.data + ", ");
} else {
sb.append(node.data + " ]");
}
node = node.link;
}
System.out.println("리스트: " + sb);
}
전체코드
package blog_doubly_linkedlist;
import list.ListI;
import java.util.NoSuchElementException;
//Doubly Linked List 구현
//맴버변수: size, head, tail
public class DoublyLinkedList<E> implements ListI<E> {
private int size; //리스트의 총 노드의 개수
private Node<E> head; //리스트의 맨 앞 노드를 가리키는 변수
private Node<E> tail; //리스트의 맨 뒤의 노드를 가리키는 변수
DoublyLinkedList() {
head = null;
tail = null;
size = 0;
}
/**
* 내부정의 클래스
*
* @param <E>
*/
private static class Node<E> {
E data;
Node<E> link;
Node<E> prev;
Node(E data) {
this.data = data;
}
}
/**
* parameter로 받은 특정 index값으로 리스트의 특정 노드를 반환하는 메서드이다.
* 여기서 linked list는 index라는 개념은 존재하지 않지만, 노드의 생성 순서에 맞게 가상의 index를 부여한다.
*
* @param index 찾고자하는 특정 index값
* @return 노드 탐색을 성공했으면 탐색한 노드를 반환한다.
* @throws IndexOutOfBoundsException index가 음수이거나 리스트의 크기보다 같거나 크다면 예외발생
*/
public Node<E> search(int index) throws IndexOutOfBoundsException {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException();
}
if (index + 1 > size / 2) {
Node<E> searchNode = tail;
for (int i = size - 1; i > index; i--) {
searchNode = searchNode.prev;
}
return searchNode;
} else {
Node<E> searchNode = head;
for (int i = 0; i < index; i++) {
searchNode = searchNode.link;
}
return searchNode;
}
}
/**
* 리스트의 전단부 맨 앞에 노드를 추가한다.
*
* @param element 새롭게 추가되는 값
*/
@Override
public void addFirst(E element) {
Node<E> newNode = new Node<E>(element);
newNode.link = head;
if (newNode.link != null) {
head.prev = newNode;
}
head = newNode;
if (size == 0) {
tail = newNode;
}
size++;
}
/**
* 리스트의 특정 index 부분에 노드를 추가한다.
* 핵심은 이전노드와 이전노드의 link노드를 새로 추가하고자 하는 노드와
* 잘 연결 시켜야한다.
*
* @param index 특정 index에 접근하는 변수
* @param element 특정 index에 넣을 값
* @throws IndexOutOfBoundsException index가 음수이거나 리스트의 크기보다 크면 예외 발생
*/
@Override
public void add(int index, E element) throws IndexOutOfBoundsException {
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException();
}
if (index == 0) {
addFirst(element);
return;
}
if (index == size) {
addLast(element);
return;
}
Node<E> prevNode = search(index - 1);
Node<E> nextNode = prevNode.link;
Node<E> newNode = new Node<E>(element);
prevNode.link = newNode;
nextNode.prev = newNode;
newNode.prev = prevNode;
newNode.link = nextNode;
size++;
}
/**
* Java에서 제공하는 링크드리스트도 add의 기본은 addLast이다.
*
* @param element list에 삽입할 값
*/
@Override
public void add(E element) {
addLast(element);
return;
}
@Override
public void addLast(E element) {
Node<E> newNode = new Node<>(element);
if (tail == null) {
head = tail = newNode;
} else {
newNode.prev = tail;
tail.link = newNode;
tail = newNode;
}
size++;
}
/**
* 특정 index에 존재하는 노드를 삭제한다.
* index 0 노드를 삭제하고자 하면 remove()를 호출한다.
*
* @param index 제거하고자 하는 특정 index값
* @return 삭제한 노드의 data 필드값을 반환한다.
* @throws IndexOutOfBoundsException index가 음수이거나 리스트의 크기보다 같거나 크면 예외 발생
*/
@Override
public E remove(int index) throws IndexOutOfBoundsException {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException();
}
if (index == 0) {
return remove();
}
Node<E> removeNode = search(index);
Node<E> prevNode = removeNode.prev;
Node<E> nextNode = removeNode.link;
E data = removeNode.data;
if (nextNode == null) {
prevNode.link = null;
tail = prevNode;
} else {
prevNode.link = nextNode;
nextNode.prev = prevNode;
}
removeNode.data = null;
removeNode.link = null;
removeNode.prev = null;
size--;
return data;
}
/**
* 특정 데이터값을 가진 노드를 삭제한다.
* 탐색한 노드가 head가 가리키는 노드라면 remove()를 호출한다.
*
* @param element 매개변수 값과 동일한 노드를 삭제한다.
* @return 삭제한 노드의 데이터 필드 값
* @throws NoSuchElementException size가 0이면 리스트가 빈 상태이므로 예외 발생
*/
@Override
public E remove(E element) throws NoSuchElementException {
if (isEmpty()) {
throw new NoSuchElementException();
}
Node<E> removeNode = head;
while (removeNode != null && !removeNode.data.equals(element)) {
removeNode = removeNode.link;
}
if (removeNode == null) {
throw new NoSuchElementException();
}
if (removeNode.equals(head)) {
return remove();
}
Node<E> nextNode = removeNode.link;
Node<E> prevNode = removeNode.prev;
if (nextNode == null) {
tail = prevNode;
prevNode.link = null;
} else {
prevNode.link = nextNode;
nextNode.prev = prevNode;
}
E returnData = removeNode.data;
removeNode.data = null;
removeNode.prev = null;
removeNode.link = null;
size--;
return returnData;
}
/**
* 리스트의 전단부 맨 앞 노드를 삭제한다.
* head가 가리키는 노드를 삭제
*
* @return 삭제한 노드의 데이터 필드 값
* @throws NoSuchElementException haed가 null이면 리스트가 빈 상태이므로 예외 발생
*/
public E remove() throws NoSuchElementException {
if (head == null) {
throw new NoSuchElementException("리스트가 빈 상태");
}
Node<E> removeNode = head;
E data = removeNode.data;
Node<E> removeNextNode = removeNode.link;
if (removeNextNode == null) {
tail = null;
head = null;
} else {
removeNextNode.prev = null;
head = removeNextNode;
}
removeNode.data = null;
removeNode.link = null;
removeNode.prev = null;
size--;
return data;
}
/**
* 공백상태는 리스트의 노드의 개수를 기록하는 size변수를 이용한다.
*
* @return size가 0이거나 0보다 작은 음수이면 true 반환
*/
@Override
public boolean isEmpty() {
return size <= 0;
}
/**
* 동적구조이므로 메모리 누수가 아닌이상 포화상태 존재하지 않는다.
*
* @return false 기본값
*/
@Override
public boolean isFull() {
System.out.println("링크드 리스트 포화상태 없다고 가정: " + Integer.MAX_VALUE);
return false;
}
/**
* 특정 노드의 데이터필드값 반환
*
* @param index 찾을 위치 index
* @return 데이터값
*/
@Override
public E get(int index) {
return search(index).data;
}
/**
* 특정 index의 노드의 E data 맴버변수 값을 변경한다.
*
* @param index 바꿀려는 index 위치 값
* @param element 바뀌어지는 값
*/
@Override
public void set(int index, E element) {
Node<E> node = search(index);
E outputData = node.data;
node.data = element;
System.out.println("기존 값: " + outputData + " 변경된 값: " + node.data);
}
/**
* 특정 값을 찾으면 index값을 반환해주는 메서드
*
* @param element 찾고자 하는 값
* @return 찾았을 경우 index 값 반환 없다면 -1반환
*/
@Override
public int indexOf(E element) throws NoSuchElementException {
Node<E> node = head;
if (size == 0) {
throw new NoSuchElementException();
}
for (int i = 0; i < size; i++, node = node.link) {
if (node.data.equals(element)) {
return i;
}
}
return -1;
}
/**
* 특정 data값을 지닌 노드가 존재하면 true 존재하지 않으면 false 반환
*
* @param element 찾고자하는 데이터 값
* @return 탐색 성공 시 true 실패 시 false
* @throws NoSuchElementException head가 null이면 검색할 노드가 존재하지 않으므로 예외발생
*/
@Override
public boolean contains(E element) throws NoSuchElementException {
if (head == null) {
throw new NoSuchElementException();
}
Node<E> node = head;
while (node != null) {
if (node.data.equals(element)) {
return true;
}
node = node.link;
}
return false;
}
/**
* size값 반환
*
* @return
*/
@Override
public int size() {
return size;
}
/**
* 리스트의 최대 크기 반환
* 동적구조이므로 int 타입의 최대값 반환
*
* @return
*/
@Override
public int capacity() {
return Integer.MAX_VALUE;
}
/**
* 리스트에 존재하는 노드의 상황을 전단부부터 후단부까지 배열형식으로 출력한다.
*/
public void toArray() {
if (size == 0) {
System.out.println("[]");
return;
}
StringBuilder sb = new StringBuilder("[");
Node<E> node = head;
for (int i = 0; i < size; i++) {
if (i != size - 1) {
sb.append(node.data + ", ");
} else {
sb.append(node.data + " ]");
}
node = node.link;
}
System.out.println("리스트: " + sb);
}
}
'Algorithm&Data Structure' 카테고리의 다른 글
| [Data Structure] 싱글 링크드 리스트 (Singly LinkedList) (0) | 2025.06.03 |
|---|---|
| [Data Structure] Array List 구현 (2) | 2025.05.21 |
| [Data Structure] 덱 (0) | 2025.05.03 |
| [Data Structure] 원형 큐 (0) | 2025.04.29 |
| [Data Structure] 큐(1) 선형 큐 구현과 단점 (0) | 2025.04.09 |