Doubly Linked List 이중 연결 리스트

* 이중 연결 리스트는 순차적으로 연결된 노드 집합으로 구성된 데이터 구조
* 각 노드가 이전 노드와 다음 노드를 가리킨다.
* 노드는 이전 노드와 다음 노드를 가리키는 두 개의 포인터로 '이중 링크'되어 있다.

public class DoublyLinkedList {

    Node head; // 첫번째 노드
    Node tail; // 마지막 노드
    int size; // 이중 연결 리스트 요소 수

    //constructor
    public DoublyLinkedList(){
        head = null;
        tail = null;
        size = 0;
    }

    //node class
    private static class Node {
        int data;
        Node prev;
        Node next;

        //constructor
        public Node(int data) {
            this.data = data;
            prev = null;
            next = null;
        }
    }

 

1. add

이중 연결 리스트에 요소를 추가하려면 지정된 데이터로 새 노드를 생성하고 리스트 끝에 추가해야 한다.

public void add(int value){

    Node newNode = new Node(value); //지정된 데이터(value)로 새 노드 생성

    if(size == 0){ //리스트가 비어있는 경우 head와 tail을 모두 새 노드로 설정
        head = newNode;
        tail = newNode;
    } else {
        tail.next = newNode; // 현재 tail 노드의 next 포인터를 새 노드로 설정
        newNode.prev = tail; //새 노드의 prev포인터를 현재 테일로 설정
        tail = newNode; //새 노드를 가리키도록 tail 업데이트
    }
    size++;
}

 

2. insert

지정된 인덱스에 지정된 값을 가진 새로운 노드를 삽입

public void insert(int index, int value){
    if(index < 0 || index > size){
        throw new IndexOutOfBoundsException("index: "+index + ", Size: "+ size);
    }

    Node newNode = new Node(value);
    if(index == 0){
        head.prev = newNode;
        newNode.next = head;
        head = newNode;
    }else if(index == size){
        tail.next = newNode;
        newNode.prev = tail;
        tail = newNode;
    }else {
        Node current = head;
        for (int i = 0; i < index - 1; i++) {
            current = current.next;
        }
        newNode.next = current.next;
        current.next.prev = newNode;
        current.next = newNode;
        newNode.prev = current;
    }
    size++;
}

 

3. remove

 지정된 데이터가 포함된 노드를 찾아 리스트에서 제거

public void remove(int data) {
    Node current = head;
    while (current != null) { //리스트를 순회하여 지정된 데이터가 포함된 노드를 찾음
        if (current.data == data) { // 찾으면 노드가 리스트의 헤드인지 테일인지 확인
            if (current.prev == null) { //헤드인 경우
                head = current.next; //다음 노드를 가리키도록 HEAD포인터를 업데이트
                if (head != null) {
                    head.prev = null; //새 헤드 노드의 prev 포인터를 null로 업데이트
                }
            } else if (current.next == null) {
                tail = current.prev;
                tail.next = null;
            } else {
                current.prev.next = current.next; //이전 노드의 next포인터를 다음 노드를 가리키도록 업데이트
                current.next.prev = current.prev; //다음 노드의 prev 포인터를 이전 노드를 가리키도록 업데이트
            }
            size--;
            return;
        }
        current = current.next;
    }
}

 

4. get

리스트를 탐색하여 지정된 데이터가 포함된 노드를 찾아야 한다.

public int get(int index){
    if(index < 0 || index >= size){ // 인덱스 유효한지 확인
        throw new IndexOutOfBoundsException();
    }
    Node current = head;
    for (int i = 0; i < index; i++) {
        current = current.next;
    }
    return current.data;
}

 

5. iterator 

이중으로 연결 리스트의 모든 요소를 반복하려면 iterator 메서드를 사용하여 새로운 iterator 객체를 반환할 수 있따.

public Iterator<Integer> iterator(){

    return new Iterator<Integer>() {

        Node current = head;

        @Override
        public boolean hasNext() {
            return current != null;
        }

        @Override
        public Integer next() {
            int data = current.data;
            current = current.next;
            return data;
        }
    };
}

 

6. size, isEmpty

//리스트의 크기를 반환한다.
public int size(){
    return size;
}

//리스트가 비어 있으면 참을 반환하고, 그렇지 않으면 거짓을 반환한다.
public boolean isEmpty(){
    return size == 0;
}