자료구조 - 양방향 연결리스트 (DoublyLinkedList) JAVA

양방향 연결리스트 의 경우는 각 노드가 head 와 Tail을 모두 가지고 있으며  각 노드는 앞 뒤 노드의 정보를 모두 가지고 있어 앞 뒤 모두 접근이 가능하다.

 

 

기본 양방향 Class JAVA 소스

class NodeBi{
    int data;
    NodeBi next;
    NodeBi prev;

    NodeBi(int data, NodeBi next, NodeBi prev){
        this.data = data;
        this.next = next;
        this.prev = prev;
    }
}
class DoulbyLinkedList extends LLlist{
    NodeBi head;
    NodeBi tail;

    DoulbyLinkedList(NodeBi node){
        this.head = node;
        this.tail = node;
    }
    public boolean isEmpty(){
        if(this.head == null){
            return true;
        }
        else
            return false;
    }

 

양방향 연결리스트는 head 와 tail 이 필요하다.

 

 

 

양방향연결리스트 데이터 추가 JAVA code

 

 public  void addData(int data ,Integer beforData){
        if(this.head == null){
            this.head = new NodeBi(data, null ,null);
            this.tail = this.head;
        }else if (beforData == null){
            this.tail.next = new NodeBi(data,null,this.tail);
            this.tail = this.tail.next;
        }else{
            NodeBi cur = this.head;
            NodeBi prev = cur;
            while (cur != null){
                if(cur.data == beforData){
                    if(cur == this.head){
                        this.head = new NodeBi(data,this.head,null);
                        this.head.next.prev = this.head;
                    }else{
                        prev.next = new NodeBi(data, cur ,prev);
                        cur.prev = prev.next;
                    }
                    break;
                }
                prev = cur;
                cur = cur.next;
            }
        }
    }

 

양방향 연결리스트에서 데이터를 추가 하는 부분이다

 

head == null 이면 Node 가 존재 하지 않는 경우 이므로 node를 생성해주고 head , tail을 할당해 준다

 

beforedata == null  인경우는 맨끝에 추가해 주는 부분이므로

 

현재 끝 tail -> next = 새로운 노드 를 가르키게 하고

현재 tail 의 위치를 tail -> next 로 할당 하여 추가해준다

 

중간 에 추가할경우 (beforeData != null )

 

head 에 추가 할경우 새로운 노드를 생성하고

추가된node -> next -> prev = head 로 재할당 시켜준다

 

node -> 추가 -> node 인경우

현재위치의 노드 와 이전 위치의 노드를 만들어 준다음에

 

cur을 순회하면서 추가하려는 위치에 조건이 되면 추가해 주는 방식이다.

 

 

그림을 나만 알아볼거같지만

 

prev -> next = 새로운 노드를 가르키게 한다.

cur -> prev = prev -> next 를 가르키게 해서 링크연결을 새롭개 구성해주어야 한다.

 

 

 

양방향 연결리스트 삭제 Java코드

 

 

 public void removeData(int data){
        NodeBi cur = this.head;
        NodeBi prev = cur;

        while (cur != null){
            if(cur.data ==data){
                if(cur == this.head && cur == this.tail){ // 현재위치가 head , tail 같은경우 노드가 하나인경우
                    this.head = null;
                    this.tail = null;
                }else if(cur == this.head){ // head 인경우 node 1 이상
                    this.head = cur.next;
                    this.head.prev = null;
                } else if (cur == this.tail){ // 가장 끝인 tail 인경우
                    this.tail = this.tail.prev;
                    this.tail.next = null;
                }else{ // 중간 노드 삭제
                    prev.next =cur.next;
                    cur.next.prev = prev;
                }
                break;
            }
            prev = cur;
            cur = cur.next;
        }
    }

 

add 하는 방식을 이해했다면 조건만 잘 나눠놨다면 삭제는 쉽다.