리스트(List) - 이중 연결 리스트(Doubly Linked List)

노드들끼리 서로 연결되어있는 리스트로, 각 노드에는 이전 노드와 다음 노드를 가리키는 참조 변수가 존재한다.

양방향 탐색이 가능하지만 단일 연결 리스트(LinkedList)보다 복잡하다

* 하지만 더 많이 쓰임

 

이중 연결 리스트(Doubly Linked List)의 구현

1. 노드 클래스 구현

class Node{
    private String data;
    public Node nextNode;
    public Node preNode;

    public Node(String data) {
        this.data = data;
        this.nextNode = null;
        this.preNode = null;
    }
    
        public String getData() {
        return this.data;
    }

}

 

2. 이중 연결 리스트 클래스 구현

class DoublyLinkedList {
    private Node head;
    private Node tail;

    public DoublyLinkedList() {
        head = null;
        tail = null;
    }
    
    public void insertNode(String data) {...}	 //노드 삽입 메서드
    public void deleteNode(String data) {...}	//노드 삭제 메서드
    public Node searchNode(String data) {...}	//노드 검색 메서드
}

 

3. 노드 삽입 메서드 구현

public void insertNode(String data) {
    Node newNode = new Node(data);
    if (head == null) {
        this.head = newNode;
        this.tail = newNode;
    } else {
        Node tempNode = this.tail;
        tempNode.nextNode = newNode;
        newNode.preNode = tempNode;
        this.tail = newNode;
    }
}

 

4. 노드 삭제 메서드 구현

public void deleteNode(String data) {
	Node currNode = head;
    Node nextNode = head.nextNode;
    Node preNode = head.preNode;
    
    if (data.equals(currNode.getData())) {
    	currNode.nextNode = null;
        head = nextNode;
        head.preNode = null;
    } else {
    	while (currNode != this.tail) {
        	if (data.equals(currNode.getData())) {
            	if (currNode.nextNode == null) {
                	currNode.preNode = null;
                    preNode.nextNode = null;
                    this.tail = preNode;
                } else {
                	preNode.nextNode = currNode.nextNode;
                    currNode.nextNode.preNode = preNode;
                    currNode.nextNode = null;
                    currNode.preNode = null;
                }
                break;
                } else {
                	preNode = currNode;
                    currNode = currNode.nextNode;
                }
            }
        }
    }
}

 

5. 노드 검색 메서드

public Node searchNode(String data) {
    Node tempNode = this.head;

    while (tempNode != this.tail) {
        if (data.equals(tempNode.getData())) {
            return tempNode;
        } else {
            tempNode = tempNode.nextNode;
        }
    }
    return tempNode;
}

 

 

 

 

관련 문제

https://www.acmicpc.net/problem/1406

1406번: 에디터