[자료구조] 리스트 - DoubleLinkedList

LinkedList는 아래 사진과 같이 Next Node만을 사용하여 Node를 관리 했었더라면

LinkedList

DoubleLinkedList는 아래 사진과 같이 Next Node와 Prev Node를 함께 사용하여 Node를 관리한다.

DoubleLinkedList

LinkedList는 맨 앞에 있는 head node 부터 마지막 node 까지 순차적으로 조회를 해야 했다면

DoubleLinkedList는 List의 절반인 중간 시점 부터 head와 가까우면 head 부터 tail과 가까우면 tail 부터 조회가 가능하다.

 

DoubleLinkedList예제

1. 우선 DoubleLinkedList도 Node를 기반으로 하기 때문에 Node를 먼저 생성

이전 LinkedList는 next Node만 관리를 해줬더라면 DoubleLinkedList는 해당 Node에 이전 Node도 관리해줘야 하므로

next Node 외에 prev Node도 함께 선언 해준다.

private class Node {
        T data;
        Node prev;
        Node next;

        Node(T data) {
            this.data = data;
        }

        Node(T data, Node prev, Node next) {
            this.data = data;
            this.prev = prev;
            this.next = next;
        }
    }

 

2. 멤버 변수를 선언하여 초기 설정 하고 생성자를 생성한다.

package list;

public class MyDoubleLinkedList<T> implements IList<T> {

    private Node head;
    private Node tail;
    private int size;

    public MyDoubleLinkedList() {
        this.size = 0;
        this.head = new Node(null);
        this.tail = new Node(null);
        this.head.next = this.tail;
        this.tail.prev = this.head;
    }

 

3. 배열 끝에 데이터를 넣어주는 add 함수 예제 (tail node가 맨 뒤 node 이므로 tail node 바로 앞에 삽입해주면 된다.)

@Override
    public void add(T t) {
        Node last = this.tail.prev;
        Node node = new Node(t, last, this.tail);
        last.next = node;
        this.tail.prev = node;
        this.size++;
    }

 

4. index를 기반으로 배열의 원하는 데이터를 가져오는 get함수 예제

@Override
    public T get(int index) {
        if(index >= this.size || index < 0) {
            throw new IndexOutOfBoundsException();
        }

        int i = 0;
        Node curr = null;
        if (index < this.size / 2) { // index 가 head 에서 더 가까우면
            curr = this.head.next;
            while (i++ < index) {
                curr = curr.next;
            }
        } else { // index 가 tail 에서 더 가까우면
            curr = this.tail.prev;
            while (i++ < (this.size = index - 1)) {
                curr = curr.prev;
            }
        }
        return null;
    }

 

5. 배열의 원하는 부분에 데이터를 넣어주는 insert함수 예제

@Override
    public void insert(int index, T t) {
        Node prev = null;
        Node curr = null;

        int i = 0;
        if(index < this.size / 2) {
            prev = this.head;
            curr = this.head.next;

            while (i++ < index) {
                prev = prev.next;
                curr = curr.next;
            }
        } else {
            curr = this.tail;
            prev = this.tail.prev;
            while (i++ < (this.size - index)) {
                curr = curr.prev;
                prev = prev.prev;
            }
        }
        
        Node node = new Node(t, prev, curr);
        curr.prev = node;
        prev.next = node;
        this.size++;
    }

 

6. 배열의 위치에 해당하는 데이터를 삭제하는 deleteByIndex함수 예제

@Override
    public boolean deleteByIndex(int index) {
        Node prev = null;
        Node curr = null;
        Node next = null;

        int i = 0;
        if(index < this.size / 2) {
            prev = this.head;
            curr = this.head.next;
            while (i++ < index) {
                prev = prev.next;
                curr = curr.next;
            }

            prev.next = curr.next;
            curr.next.prev = prev;
            curr.next = null;
            curr.prev = null;
        } else {
            // tail 에서 역으로 찾아가는 경우
            curr = this.tail.prev;
            next = this.tail;
            while (i++ < (this.size - index - 1)) {
                next = next.prev;
                curr = curr.prev;
            }
            next.prev = curr.prev;
            curr.prev.next = next;
            curr.next = null;
            curr.prev = null;
        }
        this.size--;
        return false;
    }

 

7. 파라미터 t로 받은 데이터가 배열에 존재하면 true 그렇지 않다면 false를 반환하는 contains함수 예제

@Override
    public boolean contains(T t) {
        Node curr = this.head.next;
        while (curr != null) {
            if(curr.data != null && curr.data.equals(t)) {
                return true;
            }
            curr = curr.next;
        }
        return false;
    }

 

8.  배열에 데이터가 있는지 없는지 확인하는 isEmpty함수 예제

@Override
    public boolean isEmpty() {
        return this.head.next == this.tail;
    }

 

9. contains함수와 유사하지만 데이터의 유무만 파악해주는게 아닌 존재한다면 어느 위치에 존재하는지 알려주는 indexOf함수 예제

@Override
    public int indexOf(T t) {
        Node curr = this.head.next;
        int index = 0;
        while (curr != null) {
            if(curr.data != null && curr.data.equals(t)) {
                return index;
            }
            curr = curr.next;
            index++;
        }
        return -1;
    }

 

10. 배열의 삭제하고 싶은 데이터(원하는 값)을 삭제하는 delets함수 예제

@Override
    public boolean delete(T t) {
        Node prev = this.head;
        Node curr = prev.next;
        while (curr != null) {
            if(curr.data.equals(t)) {
                prev.next = curr.next;
                curr.next.prev = prev;
                curr.next = null;
                curr.prev = null;
                this.size--;
                return true;
            }
            prev = prev.next;
            curr = curr.next;
        }
        return false;
    }