마지막 노드를 의미합니다
꼬리 노드(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;
이중 연결리스트 꼬리 노드가 없는 구조
이중 연결리스트 꼬리 노드가 있는 구조
[Stack] 배열 구현 (0) | 2020.03.30 |
---|---|
[Linked list] 리스트 결합과 데이터 중복 삭제 (0) | 2020.03.29 |
상수, N 시간 복잡도 (0) | 2020.03.21 |
HashSet : 문제적용 1 (0) | 2020.03.14 |
[Array] 기본 정리 (0) | 2020.03.09 |
댓글 영역