🧑🏻‍💻 Doubly Linked List 직접 구현 (JAVA)

💻 Knowledge/자료구조

🧑🏻‍💻 Doubly Linked List 직접 구현 (JAVA)

ming412 2023. 9. 22. 11:25

1. Doubly Linked List 자료구조

https://ming412.tistory.com/159

Singly Linked List vs Doubly Linked List vs Circular Linked List 시간복잡도 & 사용 사례

Singly Linked List (단일 연결 리스트) 각 요소가 다음 요소만 가리키는 단일 방향 구조이다. 시간 복잡도 검색 - 처음 노드(head)부터 하나씩 순회하며 원하는 값을 찾아야 하므로 O(n) 삽입 - 시작에 원

ming412.tistory.com

2. Doubly Linked List 직접 구현하기

1) ADT (Abstract Data Type) 정의

- 데이터 (Data)

- Node

- data: 데이터

- prev: 이전 노드를 참조

- next: 다음 노드를 참조

- MyDoublyLinkedList

- head: 연결 리스트의 처음 요소를 참조

- tail: 연결 리스트의 마지막 요소를 참조

- size: 연결 리스트의 길이

- 작업

- search(idx): 특정 위치의 노드 반환

- addFirst(e): 연결 리스트의 맨 앞에 요소 추가

- addLast(e): 연결 리스트의 맨 마지막에 요소 추가

- add(idx, e): 특정 위치에 요소 추가

- get(idx): 특정 위치의 노드의 값 반환

- set(idx, e): 특정 위치의 요소를 e로 변환

- removeFirst(): 연결 리스트의 맨 앞 요소 삭제

- removeLast(): 연결 리스트의 맨 끝 요소 삭제

- remove(idx): 특정 위치의 요소 삭제

2) Node 클래스 정의

단일 연결 리스트의 노드는 다음 노드의 참조(next)만 가지고 있었다.

하지만 이중 연결 리스트의 노드는 단일 연결 리스트의 노드와 다르게 이전 노드의 참조(prev)도 가지고 있다.

따라서 data와 prev, next를 선언해준다.

public class Node<E> {
	public E data;
	public Node<E> prev;
	public Node<E> next;

	public Node(E data) {
		this.data = data;
		this.prev = null;
		this.next = null;
	}
}

3) MyDoublyLinkedList 클래스 정의

이중 연결 리스트는 head와 tail 포인터로 현재 연결 리스트의 제일 첫 노드와 가장 마지막 노드를 참조하고 있다.

멤버 변수로 size를 가지고 있으면, 리스트의 길이가 궁금할 때 모든 노드를 순회하며 카운트하지 않아도 되기 때문에 편리하다.

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;
	}
}

4) search 구현

search 메서드는 add와 remove에서 사용될 내부 메서드이다.

노드를 특정 위치에 추가하거나 특정 위치에 존재하는 노드를 삭제할 때, 대상 노드를 먼저 찾아야 한다.

대상 노드를 찾을 때 사용될 예정이다.

public Node<E> search(int idx) {
    if (size < idx) {
        throw new IndexOutOfBoundsException();
    }
    Node<E> cur = head;
    for (int i=0; i<idx; i++) {
        cur = cur.next;
    }
    return cur;
}

5) add 구현

addFirst - 리스트의 맨 처음에 요소를 추가한다.

단일 연결 리스트를 구현할 때와 마찬가지로 현재 리스트에 노드가 존재하는지 혹은 리스트가 비어있는지에 따라 다르다.

현재 리스트가 비어있다면 head와 tail 모두를 newNode로 갱신하고,

비어있지 않다면 newNode와 기존 head 노드를 완벽히 연결해준 뒤 head 노드를 newNode로 갱신해야 한다.

"완벽히 연결해준다"는 말의 의미는 아래 두 가지 절차를 모두 수행해야 한다는 것이다.

1. newNode의 next가 기존 head 노드를 가리키도록 한다.

2. 기존 head 노드의 prev가 newNode를 가리키도록 한다.

단일 연결 리스트를 구현할 때는 리스트가 비어있지 않은지 확인하기 위해 if (head != null) 조건문을 사용했는데,

아래처럼 size를 이용해서 확인할 수도 있다.

public void addFirst(E data) {
    Node<E> newNode = new Node<>(data);
    if (size == 0) {
        head = tail = newNode;
    } else {
        newNode.next = head; // newNode의 next가 기존 첫 번째 노드를 가리키도록
        head.prev = newNode; // 기존 첫 번째 노드의 prev가 newNode를 가리키도록
        head = newNode; // head 노드 갱신 (tail은 그대로)
    }
    size++;
}

addLast - 리스트의 맨 끝에 요소를 추가한다.

이중 연결 리스트의 마지막에 노드를 추가할 때에는 newNode와 기존 tail 노드를 완벽히 연결해준 뒤 tail 노드를 newNode로 갱신해야 한다.

"완벽히 연결해준다"는 말의 의미는 아래 두 가지 절차를 모두 수행해야 한다는 것이다.

1. newNode의 prev가 기존 tail 노드를 가리키도록 한다.

2. 기존 tail 노드의 next가 newNode를 가리키도록 한다.

public void addLast(E data) {
    Node<E> newNode = new Node<>(data);
    if (size == 0) {
        head = tail = newNode;
    } else {
        newNode.prev = tail; // newNode의 prev가 기존 마지막 노드를 가리키도록
        tail.next = newNode; // 기존 마지막 노드의 next가 newNode를 가리키도록
        tail = newNode; // tail 노드 갱신
    }
    size++;
}

add - 리스트의 특정 위치에 요소를 추가한다.

targetNode는 newNode가 삽입되기 원하는 위치에 있는 노드를 말한다.

만약 idx가 0또는 size라면 앞서 만들었던 addFirst와 addLast를 활용할 것이다.

그게 아니라면 search(idx)를 통해 targetNode를 찾는다.

연결이 끊기지 않도록, targetNode의 이전(prev) 노드와 newNode를 먼저 연결해야 한다 ❗️

이때 targetNode의 이전 노드의 next 참조값을 newNode로 변경해야 하는데, 해당 연산이 targetNode.prev.next = newNode 이다.

그리고 newNode와 targetNode를 연결하면 된다.

public void add(int idx, E data) {
    Node<E> newNode = new Node<>(data);
    if (idx < 0 || idx > size) {
        throw new IndexOutOfBoundsException();
    }
    if (idx == 0) {
        addFirst(data);
    } else if (idx == size) {
        addLast(data);
    } else {
        Node<E> targetNode = search(idx);
        // newNode와 targetNode의 이전 노드를 연결
        targetNode.prev.next = newNode;
        newNode.prev = targetNode.prev;
        // newNode와 targetNode를 연결
        targetNode.prev = newNode;
        newNode.next = targetNode;
        
        size++;
    }
}

6) get 구현

get 함수는 특정 위치의 노드를 찾아 그 값을 반환하면 된다.

미리 만들어둔 search 함수를 이용하면 되고, idx의 범위까지 검증하자.

public E get(int idx) {
    if (idx < 0 || idx > size) {
        throw new IndexOutOfBoundsException();
    }
    return search(idx).data;
}

7) set 구현

마찬가지로 search 함수를 이용해서 idx 위치에 있는 노드를 가져온 뒤 data 값만 변경하면 된다.

public void set(int idx, E data) {
    if (idx < 0 || idx > size) {
        throw new IndexOutOfBoundsException();
    }
    search(idx).data = data;
}

8) remove 구현

removeFirst - 리스트의 맨 처음 요소를 삭제한다.

맨 처음 요소는 head 노드를 말한다.

head 노드를 삭제한다는 것은, head 노드의 바로 다음 노드가 새로운 head 노드가 되는 것이다.

따라서 head 노드의 다음(next) 노드의 prev를 null로 변경해야 한다. 해당 연산이 head.next.prev = null 이다.

그리고 리스트의 head 값을 기존 head 노드의 바로 다음 노드로 갱신하면 된다.

public void removeFirst() {
    if (size == 0) {
        throw new IndexOutOfBoundsException();
    }
    head.next.prev = null; // head 노드와 head 노드의 다음 노드와의 연결 끊기
    head = head.next; // head 노드 갱신
    size--;
}

removeLast - 리스트의 맨 끝 요소를 삭제한다.

맨 마지막 요소는 tail 노드를 말한다.

tail 노드를 삭제한다는 것은, tail 노드의 바로 앞 노드가 새로운 tail 노드가 되는 것이다.

따라서 tail 노드의 이전(prev) 노드의 next를 null로 변경해야 한다. 해당 연산이 tail.prev.next = null 이다.

그리고 리스트의 tail 값을 기존 tail 노드의 바로 앞 노드로 갱신하면 된다.

public void removeLast() {
    if (size == 0) {
        throw new IndexOutOfBoundsException();
    }
    tail.prev.next = null; // tail 노드의 이전 노드와 tail 노드의 연결 끊기
    tail = tail.prev; // head 노드 갱신
    size--;
}

remove - 리스트의 특정 위치의 요소를 삭제한다.

targetNode는 삭제할 노드를 말한다.

만약 idx가 0또는 size라면 앞서 만들었던 removeFirst와 removeLast를 활용할 것이다.

그게 아니라면 search(idx)를 통해 targetNode를 찾는다.

노드 삭제는, 삭제될 노드를 고립시키면 된다.

즉, 삭제될 노드의 앞/뒤 노드와 삭제될 노드와의 연결을 끊기만 하면 참조되지 않는 노드는 GC가 처리해준다.

targetNode 이전 노드의 next를 targetNode 다음 노드로 연결하고,

targetNode 다음 노드의 prev를 targetNode 이전 노드로 연결해 targetNode를 고립시킨다.

public void remove(int idx) {
    if (idx < 0 || idx > size) {
        throw new IndexOutOfBoundsException();
    }
    if (idx == 0) {
        removeFirst();
    } else if (idx == size - 1) {
        removeLast();
    } else {
        Node<E> targetNode = search(idx);
        targetNode.prev.next = targetNode.next; // targetNode 이전노드의 next를 targetNode 다음 노드로 연결
        targetNode.next.prev = targetNode.prev; // targetNode 다음 노드의 prev를 targetNode 이전 노드로 연결
        size--;
    }
}

9) toString 오버라이딩

아래처럼 toString을 오버라이딩하면 디버깅하기 좋다.

@Override
public String toString() {
    Node<E> cur = head;
    while (cur != null) {
        System.out.print(cur.data + " ");
        cur = cur.next;
    }
    System.out.println();
    return "MyDoublyLinkedList{" +
        "head=" + head.data +
        ", tail=" + tail.data +
        ", size=" + size +
        '}';
}

10) 전체 코드

package doubly;

import doubly.Node;

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;
	}

	public Node<E> search(int idx) {
		if (size < idx) {
			throw new IndexOutOfBoundsException();
		}
		Node<E> cur = head;
		for (int i=0; i<idx; i++) {
			cur = cur.next;
		}
		return cur;
	}

	public void addFirst(E data) {
		Node<E> newNode = new Node<>(data);
		if (size == 0) {
			head = tail = newNode;
		} else {
			newNode.next = head; // newNode의 next가 기존 첫 번째 노드를 가리키도록
			head.prev = newNode; // 기존 첫 번째 노드의 prev가 newNode를 가리키도록
			head = newNode; // head 노드 갱신 (tail은 그대로)
		}
		size++;
	}

	public void addLast(E data) {
		Node<E> newNode = new Node<>(data);
		if (size == 0) {
			head = tail = newNode;
		} else {
			newNode.prev = tail; // newNode의 prev가 기존 마지막 노드를 가리키도록
			tail.next = newNode; // 기존 마지막 노드의 next가 newNode를 가리키도록
			tail = newNode; // tail 노드 갱신
		}
		size++;
	}

	public void add(int idx, E data) {
		Node<E> newNode = new Node<>(data);
		if (idx < 0 || idx > size) {
			throw new IndexOutOfBoundsException();
		}
		if (idx == 0) {
			addFirst(data);
		} else if (idx == size) {
			addLast(data);
		} else {
			Node<E> targetNode = search(idx);
			// newNode와 targetNode의 이전 노드를 연결
			targetNode.prev.next = newNode;
			newNode.prev = targetNode.prev;
			// newNode와 targetNode를 연결
			targetNode.prev = newNode;
			newNode.next = targetNode;

			size++;
		}
	}

	public E get(int idx) {
		if (idx < 0 || idx > size) {
			throw new IndexOutOfBoundsException();
		}
		return search(idx).data;
	}

	public void set(int idx, E data) {
		if (idx < 0 || idx > size) {
			throw new IndexOutOfBoundsException();
		}
		search(idx).data = data;
	}

	public void removeFirst() {
		if (size == 0) {
			throw new IndexOutOfBoundsException();
		}
		head.next.prev = null; // head 노드와 head 노드의 다음 노드와의 연결 끊기
		head = head.next; // head 노드 갱신
		size--;
	}

	public void removeLast() {
		if (size == 0) {
			throw new IndexOutOfBoundsException();
		}
		tail.prev.next = null; // tail 노드의 이전 노드와 tail 노드의 연결 끊기
		tail = tail.prev; // head 노드 갱신
		size--;
	}

	public void remove(int idx) {
		if (idx < 0 || idx > size) {
			throw new IndexOutOfBoundsException();
		}
		if (idx == 0) {
			removeFirst();
		} else if (idx == size - 1) {
			removeLast();
		} else {
			Node<E> targetNode = search(idx);
			targetNode.prev.next = targetNode.next; // targetNode 이전노드의 next를 targetNode 다음 노드로 연결
			targetNode.next.prev = targetNode.prev; // targetNode 다음 노드의 prev를 targetNode 이전 노드로 연결
			size--;
		}
	}

	@Override
	public String toString() {
		Node<E> cur = head;
		while (cur != null) {
			System.out.print(cur.data + " ");
			cur = cur.next;
		}
		System.out.println();
		return "MyDoublyLinkedList{" +
			"head=" + head.data +
			", tail=" + tail.data +
			", size=" + size +
			'}';
	}
}

public class Main {
	public static void main(String[] args) {
		MyDoublyLinkedList<String> linkedList = new MyDoublyLinkedList<>();
		linkedList.addFirst("A");
		linkedList.addFirst("B");
		linkedList.addLast("C");
		linkedList.addLast("D");
		System.out.println(linkedList.toString());

		linkedList.add(1, "E");
		System.out.println(linkedList.toString());

		System.out.println(linkedList.get(1));
		linkedList.set(1, "F");
		System.out.println(linkedList.toString());

		linkedList.remove(3);
		linkedList.remove(0);
		System.out.println(linkedList.toString());
	}
}

'💻 Knowledge > 자료구조' 카테고리의 다른 글

LinkedList가 순환(cycle)을 가지고 있는지 어떻게 확인할까? 🐇💨 🐢 (0)	2023.09.25
🧑🏻‍💻 Doubly Linked List 직접 구현 with dummy head & dummy tail (JAVA) (0)	2023.09.25
🧑🏻‍💻 Singly LinkedList 직접 구현 (JAVA) (0)	2023.09.21
Singly Linked List vs Doubly Linked List vs Circular Linked List 시간복잡도 & 사용 사례 (0)	2023.09.21
Array vs ArrayList vs List vs LinkedList 비교 (0)	2023.09.21

현재글🧑🏻‍💻 Doubly Linked List 직접 구현 (JAVA)

Backend Developer

EMAIL. mj441@naver.com

Today :
Yesterday :

일	월	화	수	목	금	토
				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	30	31

jjamong blog