☕️ [JAVA] 다중 연결리스트 구현

자바로 다중연결리스트 구현 

 

• 생성자 

public class DoubleLinkedList<T> {
    public Node<T> head = null;
    public Node<T> tail = null;

    public class Node<T> {
        T data;
        Node<T> prev = null;
        Node<T> next = null;

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

 

인스턴스 변수 head와 tail을 선언과 초기화를 해준다. (인스턴스 생성시) 

 

Node클래스를 정의해준다. 

 

data와 

prev, next값을 만든다. 

 

생성자를 만들어준다. 인자로 받은 값을 data에 할당한다. 

 

• 데이터 추가 메서드 

public void addNode(T data) {
        if (this.head == null) {
            this.head = new Node<T>(data);
            this.tail = this.head;
        } else {
            Node<T> node = this.head;
            while (node.next != null) {
                node = node.next;
            }
            node.next = new Node<T>(data);
            node.next.prev = node;
            this.tail = node.next;
        }
    }

 

head값이 null이면 head에 Node인스턴스에 data값을 받아 인스턴스를 생성해서 할당해주고 

 

tail에 head값을 할당해준다. 

 

null이 아니면 

 

node변수에 head값을 할당해주고 

 

node.next값이 null일때 까지 반복문을 돌려서 최종적으로 변수 node에 연결리스트의 맨 끝을 할당해준다.

 

node.next에는 Node인스턴스(data를 인자로 받은)를 생성해서 할당하고 

 

node.next.prev에 node를 할당, 

 

tail에 node.next를 할당한다. 

 

• 전체 연결리스트 내용물 출력 메소드

  public void printAll(){
        if (this.head != null) {
            Node<T> node = this.head;
            System.out.println(node.data);
            while (node.next != null) {
                node = node.next;
                System.out.println(node.data);
            }
        }
    }

 

head값이 null이 아니면 변수 node에 head값을 할당해주고 프리트하고

 

node의 next값이 있으면 프린트하는 부분을 반복을 해주어서 연결리스트의 모든 요소를 출력하게 해줍니다. 

 

• head에서부터 검색

public T searchFromHead(T isData) {
        if (this.head == null) {
            return null;
        }
        Node<T> node = this.head;
        while(node != null) {
            if (node.data == isData) {
                return node.data;
            } else {
                node = node.next;
            }
        }
        return null;
    }

head값이 없으면 null을 리턴 합니다.

 

있으면 node변수에 head값을 할당, node.data가 search메소드의 인자(data)로 받은값이랑 일치하면 node(head값을 할당한)를 리턴

 

없으면 node.next의 값을 node에 할당해서 null이 될 때까지 반복문을 돌린다. 

 

끝까지 없으면 null을 반환한다. 

 

• tail부터 검색 

public T searchFromTail(T isData) {
        if (this.head == null) {
            return null;
        }
        Node<T> node = this.tail;
        while(node != null) {
            if (node.data == isData) {
                return node.data;
            }
            node = node.prev;
        }
        return null;
    }

head값이 없으면 null을 리턴 합니다.

 

있으면 node변수에 tail값을 할당, node.data가 search메소드의 인자(data)로 받은값이랑 일치하면 node(tail값을 할당한)를 리턴

 

없으면 node.prev의 값을 node에 할당해서 null이 될 때까지 반복문을 돌린다. 

 

끝까지 없으면 null을 반환한다. 

 

• 데이터 중간에 삽입 

public boolean insertToFront(T existedData, T addData){
        if (this.head == null) {
            this.head = new Node<T>(addData);
            this.tail = this.head;
            return true;
        } else if (this.head.data == existedData) {
            Node<T> newHead = new Node<T> (addData);
            newHead.next = this.head;
            this.head = newHead;
            this.head.next.prev = this.head;
            return true;
        } else {
            Node<T> node = this.head;
            while (node != null) {
                if (node.data == existedData) {
                    Node<T> nodePrev = node.prev;
                    
                    nodePrev.next = new Node<T>(addData);
                    nodePrev.next.next = node;
                    
                    nodePrev.next.prev = nodePrev;
                    node.prev = nodePrev.next;
                    return true;
                } else {
                    node = node.next;
                }
            }
            return false;
        }
    }

코드가 길지만 찬찬히 살펴보자 

 

메소드 insertToFront는 검색할 대상(existedData)과 삽입할 데이터(addData)를 인자로 받는 메소드 이다. 

 

head값이 null이면 head에 Node인스턴스에 addData값을 받아 인스턴스를 생성해서 할당해주고

 

tail에 head값을 할당해준다. 

 

null이 아니고 만약 head.data값이 검색할 대상(existedData)과 같다면 삽입할 데이터를 newHead라는 변수에 인스턴스를 생성해서 할당하고

 

newHead.next에 this.head를 할당, this.head에 newHead할당, this.head.next.prev에 this.head할당 해주고 true를 리턴한다. 

 

null이 아니고 만약 head.data값이 검색할 대상(existedData)과 다르다면 

 

변수node에 this.head를 할당해주고 node값이 null이 아닐 때까지 반복문을 돌린다.

 

만약 node.data값이 검색할 대상(existedData)과 같다면 

 

변수 nodePrev에 node.prev값을 임시로 저장하고 

 

nodePrev.next에 새로 생성한 Node인스턴스를 할당한다. 

 

nodePrev.next.next에 node를 할당해서 node앞에 새로운 인스턴스가 끼워지게 만든다. 

 

nodePrev.next.prev에는 nodePrev를 node.prev에는 nodePrev.next값을 할당하여 이어준다. 

 

그림으로 그려보자면 

 

 

 

• 최종 코드

public class DoubleLinkedList<T> {
    public Node<T> head = null;
    public Node<T> tail = null;

    public class Node<T> {
        T data;
        Node<T> prev = null;
        Node<T> next = null;

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

    public void addNode(T data) {
        if (this.head == null) {
            this.head = new Node<T>(data);
            this.tail = this.head;
        } else {
            Node<T> node = this.head;
            while (node.next != null) {
                node = node.next;
            }
            node.next = new Node<T>(data);
            node.next.prev = node;
            this.tail = node.next;
        }
    }

    public void printAll(){
        if (this.head != null) {
            Node<T> node = this.head;
            System.out.println(node.data);
            while (node.next != null) {
                node = node.next;
                System.out.println(node.data);
            }
        }
    }

    public T searchFromHead(T isData) {
        if (this.head == null) {
            return null;
        }
        Node<T> node = this.head;
        while(node != null) {
            if (node.data == isData) {
                return node.data;
            } else {
                node = node.next;
            }
        }
        return null;
    }

    public T searchFromTail(T isData) {
        if (this.head == null) {
            return null;
        }
        Node<T> node = this.tail;
        while(node != null) {
            if (node.data == isData) {
                return node.data;
            }
            node = node.prev;
        }
        return null;
    }

    public boolean insertToFront(T existedData, T addData){
        if (this.head == null) {
            this.head = new Node<T>(addData);
            this.tail = this.head;
            return true;
        } else if (this.head.data == existedData) {
            Node<T> newHead = new Node<T> (addData);
            newHead.next = this.head;
            this.head = newHead;
            this.head.next.prev = this.head;
            return true;
        } else {
            Node<T> node = this.head;
            while (node != null) {
                if (node.data == existedData) {
                    Node<T> nodePrev = node.prev;

                    nodePrev.next = new Node<T>(addData);
                    nodePrev.next = node;

                    nodePrev.next.prev = nodePrev;
                    node.prev = nodePrev.next;
                    return true;
                } else {
                    node = node.next;
                }
            }
            return false;
        }
    }
}