[자료구조] Doubly Linked List

Doubly Linked List

지난 포스팅에서 언급했던 Singly Linked List을 보완하여 정의된 Doubly Linked List이다.

단일 링크드 리스트와 다르게 한쪽 방향으로만 pointer가 있는 것이 아닌 좌우로 pointer가 존재한다.
좌우로 pointer를 표현했기 때문에 좀던 자유롭게 Node에 접근할 수 있다. 

 

아래는 지난 글인 Single Linked List이다.

jsy-coding-blog.tistory.com/9

[자료구조] Single Linked List

Doubly Linked List 설계

Node 설계

Doubly Linked List의 Node는 단일연결리스트와 다르게 Node pointer가 2개가 존재해야 한다. 그 외에는 Singly Linked List와 동일하다.
아래는 그림으로 표현한 Doubly Linked List의 Node이다.

 

위 그림처럼 Node를 코드로 작성해보자

class dNode
{
    int data;
    dNode left, right;

    //생성자
    public dNode(int data)
    {
        this.data = data;
        left = right = null;
    }
}

Node의 pointer가 2개인 것을 제외하면 Singly Linked List와 동일하다.

Linked List 설계

이제는 Doubly Linked List를 설계해 보자. Linked List에서 사용하는 메소드를 적용한다. 삽입,삭제,검색,출력 등등이 있겠다. 또한 멤버 변수로는 첫번째 요소를 가리키는 pointer인 head pointer가 존재해야 할 것이다. 아래는 구현할 Linked List의 스켈레톤 코드이다.

class DoublyLinkedList
{
    private int len;
    private dNode head;

    public DoublyLinkedList() {} //생성자
    public boolean isEmpty() {} //List가 비어있는지를 판단
    public int length() {} //현재 List의 길이를 반환
    public void insert(int data) {} //데이터를 삽입하는 메소드
    public void delete(inte data) {} //데이터를 삭제하는 메소드
    public int search(int data) {} //데이터를 탐색하여 발견된 index를 반환하는 메소드
    public String toString() {} //출력을 위한 toString 오버라이드
    public void print() {} //Linked List를 출력하는 메소드
}

생성자 및 기타 메소드는 이전에 올렸던 Single Linked List를 참고하면 되겠다.

삽입

삽입은 이전에 소개했던 Single Linked List에서의 while 반복을 통한 Node의 이동을 통해서 구현하면 된다. 바로 코드를 확인해 보자

public void insert(int data)
{
    if(this.isEmpty()) {head = new dNode(data);} //리스트가 비어있으면 head에 새로운 Node 삽입
    else
    {
        dNode p = head; //Node p를 마지막 노드까지 이동시킨다.

        // p의 오른쪽 Node pointer가 null(비어있다.)일때 까지 반복
        // p=p.right는 오른쪽으로 p를 이동시키는 것을 표현함
        while(p.right != null) {p = p.right;}

        // 새로운 Node temp 선언
        dNode temp = new dNode(data);

        //마지막 Node p와 새로운 Node temp를 서로 연결
        p.right = temp;
        temp.left = p;
    }
    len++;
}

주석을 잘 확인하면서 코드를 확인하길 바란다. 우선 head를 가리키는 pointer Node p를 선언하고 p를 마지막 노드로 이동시킨다.(right) 그리고 마지막 노드라고 확인이 되면 새로운 Node temp를 생성해 p의 오른쪽과 tmep의 왼쪽을 연결하여 List에 요소를 삽입한다. 아래 그림을 통해 표현하면 이렇다.

삭제

삭제도 기존의 Single Linked List와 로직은 동일하다 하지만 2개의 Node pointer를 사용했던 단일연결리스트와 달리 1개의 Node pointer를 사용하면 된다.

삭제에 대한 경우의 수를 나누어 보았다.
1. 삭제할 노드가 head일 경우
2. 삭제할 노드가 List의 가운데 있을 경우(좌우 pointer가 null이 아닐 경우)
3. 삭제할 노드가 List의 맨 끝에 있을 경우
4. 삭제할 노드가 없을 경우

위 경우의 수를 적용하여 코드로 나타내보았다.

public void delete(int data)
{
    if(this.isEmpty()) {System.out.println("List is empty");}
    else
    {
        dNode p = head;

        if(head.data == data) //삭제할 노드가 head일 경우
            {head = head.right;}
        else
        {
            // 삭제할 노드로 이동
            // p의 right가 null이거나 p의 data가 삭제할 data와 같을때 까지 반복
            while(p.right != null && p.data != data) 
                {p = p.right;}

            if(p.right != null) // 삭제할 노드가 가운데 있을 경우
            {    
                p.left.right = p.right;
                p.right.left = p.left;
            }
            else if(p.right == null) // 삭제할 노드가 끝에 있을 경우
                {p.left.right = null;}
            else {System.out.println("Not found");} //삭제할 노드가 없을 경우
        }
        p = null;
        len--;
    }
}

코드에서 p.left.right 같이 pointer를 여러번 쓴 경우를 확인 할 수 있다. 이를 해석해 보면 "Node P의 왼쪽 Node의 오른쪽 Node" 정도가 되겠다. "."을 "의"로 해석하면 좀더 직관적으로 해석 할 수 있지 않을까 싶다.

검색

검색 메소드는 delete와 매우 유사하다. 단지 삭제를 하지 않은 것이 차이다.(반복되는 코드를 따로 정리할 수 있을거 같은데... ㅍ_ㅍ;)
바로 코드를 확인해 보자

public int search(int data)
{
    int idx = 0; //반환할 index 변수

    if(this.isEmpty()) {System.out.println("List is empty"); return -1;}
    else
    {
        dNode p = head;
        if(head.data == data) {return 0;}
        else
        {
            while(p.right != null && p.data != data) 
                {p = p.right; idx++;}

            if(p.right != null) // 탐색할 노드가 가운데 있을 경우
                {return idx;}
            else if(p.right == null && p.data == data) // 탐색할 노드가 끝에 있을 경우
                {return len-1;}
            else {System.out.println("Not found"); return -1;}
        }
    }

delete와 매우 유사하므로 설명을 생략하고자 한다.\

전체 코드

전체 코드는 아래 github 링크에서 확인 할 수 있다.

github.com/JoSangYeon/Algorithm/blob/master/LinkedList/DLL.java

JoSangYeon/Algorithm

main메소드를 제외한 코드는 아래와 같다.

class dNode
{
    int data;
    dNode left, right;

    public dNode(int data)
    {
        this.data = data;
        left = right = null;
    }
}

class DoublyLinkedList
{
    private int len;
    private dNode head;

    public DoublyLinkedList()
    {
        len = 0;
        head = null;
    }

    public boolean isEmpty() {return head == null && len == 0;}
    public int length() {return this.len;}

    public void insert(int data)
    {
        if(this.isEmpty()) {head = new dNode(data);}
        else
        {
            dNode p = head;
            while(p.right != null) {p = p.right;}

            dNode temp = new dNode(data);

            p.right = temp;
            temp.left = p;
        }
        len++;
    }

    public void delete(int data)
    {
        if(this.isEmpty()) {System.out.println("List is empty");}
        else
        {
            dNode p = head;

            if(head.data == data)
                {head = head.right;}
            else
            {
                while(p.right != null && p.data != data) 
                    {p = p.right;}

                if(p.right != null) // 삭제할 노드가 가운데 있을 경우
                {    
                    p.left.right = p.right;
                    p.right.left = p.left;
                }
                else if(p.right == null) // 삭제할 노드가 끝에 있을 경우
                    {p.left.right = null;}
                else {System.out.println("Not found");}
            }
            p = null;
            len--;
        }
    }

    public int search(int data)
    {
        int idx = 0;

        if(this.isEmpty()) {System.out.println("List is empty"); return -1;}
        else
        {
            dNode p = head;
            if(head.data == data) {return 0;}
            else
            {
                while(p.right != null && p.data != data) 
                    {p = p.right; idx++;}

                if(p.right != null) // 탐색할 노드가 가운데 있을 경우
                    {return idx;}
                else if(p.right == null && p.data == data) // 탐색할 노드가 끝에 있을 경우
                    {return len-1;}
                else {System.out.println("Not found"); return -1;}
            }
        }
    }

    public String toString()
    {
        String result = "[ ";

        dNode p = head;

        while(p != null)
        {
            result += p.data + " ";
            p = p.right;
        }
        result += "]";

        return result;
    }

    public void print()
        {System.out.println(this.toString());}
}

결론

Doubly Linked List는 tree와 graph등 다음 자료구조에서 사용하는 Node 구조와 똑같다. 그래서 Singly 보다는 Double의 구조를 좀더 이해할 필요가 있다. 다음 포스팅에서는 기본적인 Tree의 정의와 BST를 구현해보겠다!

 

 

혹시 틀린 부분이나 궁금한 부분은 댓글에 남겨주세요~ -JSY-