지난 글에서는 단일 연결 리스트(Singly Linked List)에 대해서 알아보았습니다.
Doubly Linked List는 양방향 연결 리스트로, node 클래스에 이전 node를 가리키는 prev 변수와 다음 node를 가리키는 next 변수가 있습니다.
DoublyListNode를 코드로 표현하면 다음과 같습니다. next는 다음 node를, prev는 이전 node를 가리킵니다.
class DoublyListNode {
int val;
DoublyListNode next, prev;
DoublyListNode(int x) {val = x;}
}이 리스트도 head를 갖고 있습니다. 다른 node를 찾을 때 head부터 시작해야 합니다.
Doubly Linked List 구현하기
Doubly Linked List를 코드로 구현해보면서 설명을 하겠습니다.
Doubly Linked List 클래스는 다음과 같은 함수들을 제공합니다.
- int get(int index) : 인자로 전달되는 index의 데이터를 리턴
- void addAtHead(int val) : node를 리스트의 맨 앞에 추가
- void addAtTail(int val) : node를 리스트 마지막에 추가
- void addAtIndex(int index, int val) : 특정 index에 node를 추가
- void deleteAtIndex(int index) : 특정 index의 node를 삭제
다음과 같이 위의 메소드들을 포함하는 MyLinkedList라는 클래스를 만들었습니다. 지금은 메소드만 정의되어있고, 메소드 내부의 코드는 구현되지 않았습니다.
class MyLinkedList {
DoublyListNode head = null;
public MyLinkedList() {
}
public int get(int index) {
}
public void addAtHead(int val) {
}
public void addAtTail(int val) {
}
public void addAtIndex(int index, int val) {
}
public void deleteAtIndex(int index) {
}
}위의 코드는 Leetcode - Doubly Linked List에서 가져왔습니다.
Leetcode에서 자신이 구현한 코드를 여러 테스트 케이스로 검증할 수 있습니다. 모든 테스트 케이스를 통과할 때까지 직접 구현해보세요.
구현된 코드를 먼저 보시려면 GitHub - DoublyLinkedList에서 확인하시면 됩니다.
addAtHead() : 리스트 맨 앞에 추가
addAtHead()는 리스트의 맨 앞에 node를 추가하는 메소드입니다.
맨 앞에 node를 추가하는 것은 Singly Linked List와 유사합니다. 차이점은 Doubly Linked List는 prev를 갖고 있기 때문에 이것도 설정을 해줘야 합니다.
다음과 같은 리스트가 있을 때, 먼저 node를 생성합니다.
그리고 다음과 같이 node의 next와 head의 prev를 연결해 줍니다.
마지막으로 head를 node로 변경해 줍니다.
다음은 위의 내용을 코드로 구현한 것입니다.
public void addAtHead(int val) {
if (head == null) {
head = new DoublyListNode(val);
return;
}
DoublyListNode node = new DoublyListNode(val);
node.next = head;
head.prev = node;
head = node;
}get(index) : index의 데이터를 리턴
get()은 인자로 전달된 index의 node를 찾고 그 데이터를 리턴해주는 메소드입니다.
다음과 같이 for를 이용하여 해당하는 index를 찾고 그 결과를 리턴하도록 구현하면 됩니다.
/** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */
public int get(int index) {
if (head == null) {
return -1;
}
DoublyListNode cur = head;
for (int i = 0; i < index; i++) {
if (cur.next == null) {
return -1;
}
// Move to Index (i + 1)
cur = cur.next;
}
return cur.val;
}다음 케이스에 대해서 예외처리가 필요합니다.
- head가 null인 경우 -1을 리턴
- 리스트 길이가 index보다 큰 경우
addAtTail(val) : 리스트 맨 마지막에 추가
addAtTail()는 리스트의 가장 마지막에 node를 추가하는 메소드입니다.
먼저 리스트의 마지막으로 이동하고, 그리고 node를 생성합니다.
마지막 node와 새로운 node의 prev와 next를 연결해 줍니다.
다음은 위의 내용을 코드로 구현한 것입니다.
/** Append a node of value val to the last element of the linked list. */
public void addAtTail(int val) {
if (head == null) {
head = new DoublyListNode(val);
return;
}
DoublyListNode cur = head;
while (cur.next != null) {
cur = cur.next;
}
DoublyListNode node = new DoublyListNode(val);
cur.next = node;
node.prev = cur;
}다음 케이스에 대해서 예외처리가 필요합니다.
- head가 null일 때, head에 새로운 node를 할당
addAtIndex(index, val) : 특정 index에 node 추가
addAtIndex()는 리스트의 특정 index의 위치에 node를 추가하는 메소드입니다.
먼저 특정 index의 node(cur)를 찾습니다.
prev node와 새로 생성한 node를 연결하고, 생성한 node와 cur node를 연결합니다.
다음은 위의 내용을 코드로 구현한 것입니다.
/** Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list,
* the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted. */
public void addAtIndex(int index, int val) {
if (head == null) {
if (index == 0) {
head = new DoublyListNode(val);
}
return;
}
DoublyListNode prev = null;
DoublyListNode cur = head;
for (int i = 0; i < index; i++) {
if (cur == null) {
return;
}
// Move to Index (i + 1)
prev = cur;
cur = cur.next;
}
DoublyListNode node = new DoublyListNode(val);
if (prev == null) {
node.next = head;
head.prev = node;
head = node;
} else if (cur == null) {
cur = node;
prev.next = cur;
cur.prev = prev;
} else {
prev.next = node;
node.prev = prev;
node.next = cur;
cur.prev = node;
}
}다음 케이스에 대해서 예외처리가 필요합니다.
- head가 null일 때 index가 0이면 node 추가, 그렇지 않으면 추가하지 않음
- 리스트 길이가 index와 동일한 경우, node 추가
- 리스트 길이보다 index가 큰 경우, 추가하지 않음
index 0에 node를 추가할 수도 있으며, 리스트의 가장 마지막에 node를 추가할 수도 있습니다. 여러 케이스를 고려해야 합니다.
deleteAtIndex(index) : 특정 index의 node를 삭제
deleteAtIndex()는 특정 index의 node를 삭제하는 메소드입니다.
먼저 특정 node(cur)를 찾습니다.
그리고 특정 node의 prev와 next를 연결해주면 cur node는 삭제가 됩니다.
다음은 위의 내용을 구현한 코드입니다.
/** Delete the index-th node in the linked list, if the index is valid. */
public void deleteAtIndex(int index) {
if (head == null) {
return;
}
DoublyListNode cur = head;
for (int i = 0; i < index; i++) {
if (cur.next == null) {
return;
}
// Move to Index (i + 1)
cur = cur.next;
}
DoublyListNode prev = cur.prev;
DoublyListNode next = cur.next;
if (prev == null) {
head = next;
} else if (next == null) {
prev.next = null;
} else {
prev.next = next;
next.prev = prev;
}
}다음 케이스에 대해서 예외처리가 필요합니다.
- head가 null이면 node를 삭제하지 않음
- index의 범위를 초과하면 node를 삭제하지 않음
전체 코드
완성된 코드는 GitHub - DoublyLinkedList에서 확인할 수 있습니다.
검증(Verification)
먼저 자신이 구현한 코드가 아래와 같은 간단한 테스트 케이스를 통과하는지 확인할 수 있습니다.
MyLinkedList linkedList = new MyLinkedList(); // Initialize empty LinkedList
linkedList.addAtHead(1);
linkedList.addAtTail(3);
linkedList.addAtIndex(1, 2); // linked list becomes 1->2->3
System.out.println(linkedList.get(1)); // returns 2
linkedList.deleteAtIndex(1); // now the linked list is 1->3
System.out.println(linkedList.get(1)); // returns 3다음과 같이 출력되면 이 테스트 케이스는 패스한 것입니다.
2
3그리고 Leetcode - Doubly Linked List에서 더 많은 테스트 케이스로 검증할 수 있습니다.
사이트에 자신의 코드를 붙여넣고 submit 버튼을 누르면 테스트 결과를 보여줍니다.
참고
Related Posts
- LeetCode - Check If N and Its Double Exist (Searching)
- 양방향 연결 리스트(Doubly Linked List) 설명과 예제 코드(Java)
- 단일 연결 리스트(Singly Linked List) 설명과 예제 코드(Java)
- Algorithm - Prefix Sum은 무엇이고 언제 필요할까요?
- 원형 연결 리스트(Circular Linked List) 설명과 예제 코드(C++)
- 양방향 연결 리스트(Doubly Linked List) 설명과 예제 코드(C++)
- 단일 연결 리스트(Singly Linked List) 설명과 예제 코드(C++)