상세 컨텐츠

본문 제목

[Linked list] 이중 연결리스트 꼬리 노드

본문

꼬리 노드 의미 (tail node)

마지막 노드를 의미합니다


이중 연결리스트 꼬리 노드 장점 (tail node)

꼬리 노드(tailNode)를 저장하고 있어 이중 연결리스트의 마지막 노드를 삽입하고 삭제하는 시간이 빠릅니다.

시간 복잡도 : 마지막 노드삽입 O(1) , 마지막 노드삭제 O(1)

    public DoublyLinkedList<T>{
        public class Node{ ... } 

        public Node headNode;
        public Node tailNode;
        public int size;
    }

다만, 단순 연결리스트(Singly linked list)는 마지막 노드를 삭제하는데 O(n) 시간이 소요됩니다.

삭제하기 전 마지막 노드의 이전 노드를 탐색하는 시간이 필요합니다.

    while(currentNode.nextNode != tailNode && currentNode.nextNode != null){
        currentNode = currentNode.nextNode;
    }

    if(currentNode.nextNode == tailNode){
        currentNode.nextNode = null;
        tailNode = currentNode;
    }

단순 연결리스트 마지막 노드 삽입은 O(1) 시간이 소요됩니다.

    tailNode = insertNode;
    currentNode.nextNode = tailNode;


이중 연결리스트 (Doubly linked list)

이중 연결리스트 꼬리 노드가 없는 구조



이중 연결리스트 꼬리 (Doubly linked list tail)

이중 연결리스트 꼬리 노드가 있는 구조



관련글 더보기

댓글 영역