티스토리 뷰

베니의 자료구조 - 이중 연결 리스트(Doubly Linked List)

베니는 생활코딩 이고잉님의 자료구조 강의, 구글링을 통해 자료구조를 공부하고 있습니다.  
인용하는 내용의 출처는 링크를 남겨놓고 있습니다.
도움 주신 모든분들께 감사드립니다!

생활코딩 이고잉님

목차

1. 정의

2. 특징

3. 활용

4. 베니의 생각

Doubly Linked List는 공간이 3개입니다!


1. 정의

 

이중 연결리스트는 단순 연결리스트에서 previous 영역이 추가되어 확장이 된 자료구조이다.

 


2. 특징

(1) Next만 가지고 있는 단순 연결리스트와는 다르게 Next와 Previous 모두 가지고 있어 양방향으로 탐색이 가능하다

- 단순 연결리스트는 Next를 통해 하나의 방향으로 탐색을 하지만 이중 연결리스트는 Previous 영역이 추가됩니다.

 

(2) Previous를 유지가 필요하므로 더 많은 메모리 공간을 차지한다.

- Previous 또한 메모리를 차지하기 때문에 노드 1개 당 하나의 메모리를 추가적으로 사용하게 됩니다.

 

 


3. 활용

이중 연결 리스트는 previous가 추가되었기 때문에 모든 기능에 previous가 추가됨과 동시에

추가된 경우에 대한 고려가 필요합니다.

 

 

(1) add

// 가장 처음 Index에 노드 추가
public void addFirst(Object input){
	Node newNode = new Node(input); 
    newNode.next = head;
    
    // prev가 추가 됬으므로 현재 head의 prev는 새로운 추가한 노드가 되며
    // 이는 head가 null이 아닐 때 즉 새로 추가한 노드까지 2개 이상일 때 실행됩니다.
    if(head != null){
    	head.prev = newNode;
    }
    
    head = newNode;
    size++;
    if(head.nect == null){
    	tail = head;
    }
}

먼저 리스트의 가장 앞에 노드를 추가하는 addFirst 메서드입니다.

head가 null이 아닐 때 head의 prev 영역에 새로운 노드를 연결하는 코드가 추가되었습니다.

 

// tail에 연결되는 새로운 노드를 추가합니다
public void addLast(Object input){
	Node newNode = new Node(input);
    if(size == 0){
    	addFirst(input);
    } else {
      tail.next = newNode;
      newNode.prev = tail; // tail이었던 값을 newNode의 prev로 연결합니다
      tail = newNode;
      size++;
    }
}

반대로 가장 뒤에 노드를 추가하는 addLast 메서드는 tail이었던 값을

새로운 노드의 previous로 연결하는 코드가 추가되었습니다.

 

// 인덱스 k의 위치에 노드를 추가합니다.
public void add(int k, Object input){
	if(k == 0){
    	addFirst(input);
    } else {
    	Node temp1 = node(k-1);
        Node temp2 = temp1.next;
        Node newNode = new Node(input);
        temp1.next = newNode;
        newNode.next = temp2;
        
        // 인덱스 k 위치에 노드가 있을 때
        if(temp2 != null){
        	temp2.prev = newNode; // k의 노드의 prev로 새로운 노드를 연결합니다
        }
        newNode.prev = temp1; // 새로운 노드의 prev로 k-1에 위치한 노드를 연결합니다
        
        size++;
        if(newNode.nect == null){
        	tail = newNode;
        }
    }
}

원하는 위치에 노드를 추가하는 add 메서드입니다.

새로운 노드의 previous와 새로운 노드의 next 노드인 temp2의 previous를 연결해줍니다.

 

 

// index 위치의 노드 탐색 시
Node node(int index){
	
    // 탐색하려는 노드의 index가  size/2로 계산되는 중간 index보다 작으면
	if(index < size/2){
        // head부터 탐색을 진행
    	Node x = head;
        for(int i=0; i < index; i++){
        	x = x.next;
        }
        return x;
    // 중간 index보다 크면
    } else {
    	// tail부터 탐색을 진행
    	Node x = tail;
        for(int i = size-1; i > index; i--){
        	x = x.prev;
        }
        return x;
    }
    
}

노드의 탐색 방법 또한 달라집니다.

index의 위치에 있는 노드를 찾고 싶을 때 단방향 연결리스트는 head부터 시작해서 next를 통해 탐색을 하지만

이중 연결리스트는 index가 리스트의 중간 index 크기보다 클 때에는 tail에서 시작하여 prev를 통해

탐색을 할 수 있으므로 시간 복잡도가 O(n)에서 O(log n)으로 줄어들게 됩니다.

 

public Object removeFirst() {
	Node temp = head;
    head = head.next;
    Object return Data = temp.data;
    temp = null;
    if(head != null){
    	head.prev = null;
    }
    size--;
    return returnData;
}

그리고 가장 첫번째 노드를 삭제하는 removeFirst 메서드입니다.

head가 null이 아닐 때 head의 prev이 null이 됩니다.

 

public Object remove(int k){
	if(k == 0){
    	return removeFirst();
    }
    
    Node temp = node(k-1);
    Node todoDeleted = temp.next;
    temp.next = temp.next.next;
    
    // temp의 next가 있다면
    if(temp.next != null){
    	temp.next.prev = temp; // temp의 next의 prev는 temp를 가리킵니다.
    }
    Object returnData = todoDeleted.data;
    if(todoDeleted == tail){
    	tail = temp;
    }
    todoDeleted = null;
    size--;
    return returnData;
}

원하는 위치의 노드를 삭제하는 remove 메서드입니다.

temp는 index 위치의 전 노드를 의미하고 temp의 next.next 노드를 temp의 next로 연결한 후

temp의 next가 있다면 temp의 next 노드의 prev는 temp로 연결이 되게 됩니다.

 

public ListIterator listIterator(){
    return new ListIterator();
}

public class ListIterator{
    private Node next;
    private Node lastReturned;
    private int nextIndex;
    
    ListIterator(){
    	next = head;
    }
    
    public Object next(){
        lastReturned = next;
        next = next.next;
        nextIndex++;
        return lastReturned.data;
    }
    
    // previous가 가능한지 확인
    public boolean hasPrevious(){
        // nextIndex가 0보다 크다는 것은 현재 첫번째 노드를 가리키는게 아닌 것을 의미합니다.
        return nextIndex > 0; 
    }
    
    // previous 메서드 추가
    public Object previous(){
    	// next가 없을 때는
    	if(next == null){
            lastReturned = next = tail // 마지막 리턴과 next 둘 다 tail을 가리킵니다.
        // 있을 때에는
        } else {
            lastReturned = next = next.prev; // 마지막 리턴과 next 둘 다 next의 prev를 가리킵니다.
        }
        nextIndex--; // next를 가리키는 index 값을 줄이고
        return lastReturned.data;  // 마지막 리턴한 데이터 출력합니다.
    }
	
    public boolean hasNext(){
    	return nextIndex < size();   
    }
}

Iterator는 양방향 리스트로 구현 시 previous 메서드와 hasPrevious 메서드가 추가가 되며 

next와는 반대로 리스트의 앞으로 nextIndex가 이동을 하며 이전 값들을 반환합니다.

 

public void add(Object input){
    Node newNode = new Node(input);
    
    if(lastReturned == null){
    	head = newNode;
        newNode.next = next;
    } else {
    	lastReturned.next = newNode;
        
        // newNode의 prev는 lastReturned가 됩니다.다.
        newNode.prev = lastReturned;
        // 마지막 노드가 아니라면
        if(next != null){
            newNode.next = next; // next는 newNode의 next가 되고
            next.prev = newNode; // newNode는 next의 prev가 됩니다.
            
        // 마지막 노드라면
        } else {
            tail = newNode; // newNode는 tail이 됩니다.
        }

    }
    
    alstReturned = newNode;
    nextIndex++;
    size++;
}

 

remove

public void remove(){
	
    // next를 호출하지 않은 상태에서 삭제를 하려고 할 때
    if(nextIndex == 0){
    	throw new IllegalStateException(); // 예외처리 진행
    }
    
    Node n = lastReturned.next; // 마지막 리턴한 노드의 다음 노드
    Node p = lastReturned.prev; // 마지막 리턴한 노드의 전 노드
    
    // 전 노드가 없을 때는
    if(p == null){ 
    	head = n; // 삭제한 노드의 다음 노드가 head가 되고
        head.prev = null; // head의 prev는 없고
    	lastReturned = null; // 마지막 반환 값 또한 없습니다.
    // 전 노드가 있을 때는 중간 노드나 마지막 노드를 삭제한 것이므로
    } else {
    	p.next = next; // 삭제한 노드의 전 노드가 next 값이 되고
        lastReturned.prev = null; // lasReturned의 prev가 없어집니다.
    }
    
    // 마지막 노드를 삭제하였을 때
    if(n == null){
    	tail = p; // tail은 p 노드가 되며
        tail.next = null; // tail의 next는 없습니다.
    // 마지막 노드를 삭제한 것이 아니라면
    } else {
    	n.prev = p; // 삭제한 노드 다음 노드의 prev는 삭제한 노드의 전 노드를 가리킵니다.  
    }
    
    // 다음 노드가 없으면
    if(next == null){
    	lastReturned = tail; // lasReturned 는 tail을 가리키고
    // 다음 노드가 있다면
    } else {
    	lastReturned = next.prev; // lastReturned는 다음 노드의 prev 경로를 가리킵니다.
    }
    
    size--; // 삭제하였으므로 사이즈가 줄어들고
    nextIndex--; // next의 Index가 감소합니다.
}

remove 메서드는 기존 next만 사용하던 remove와는 많은 차이가 있었습니다.

head와  tail이 가리키는 데이터 또한 변경이 되었으며 복잡하기도 합니다.

 


4. 베니의 생각

공부하고 글을 쓸수록 많은 이해력을 요구하는 내용들을 만나게 되는 것 같습니다.
처음에는 정말 하나도 이해가 안되고 지루한 내용들이라고 생각이 된 것도 있었는데 ( 특히 Iterator가 그랬습니다.. )
다음에 한 번 더 강의를 듣게 될 때는 조금 더 이해하게 되어 반복의 중요성에 대해서 다시 한 번 깨닫는
시간이 되었던 것 같습니다. 

글을 쓰는 주기가 길다보니 전의 글의 내용이 기억이 나지 않을 때가 있는데 이것 또한 반복을 통해
완전히 머리 속에 저장할 수 있도록 하겠습니다!

처음에는 정말 멀게만 느껴지고 깜깜했던 과정이 작지만 한걸음한걸음 내딛으니 성장한다는 느낌을 받습니다!
앞으로도 더 화이팅하도록 하며 글과 공부를 게을리하지 않겠습니다!

TODO
- 스택(Stack)
댓글
댓글쓰기 폼
공지사항
최근에 달린 댓글
Total
377
Today
0
Yesterday
0
링크
«   2020/08   »
            1
2 3 4 5 6 7 8
9 10 11 12 13 14 15
16 17 18 19 20 21 22
23 24 25 26 27 28 29
30 31          
글 보관함