Stack을 Linked List로 구현할 경우 Head에서 push(), pop()을 진행한다. Head가 아닌 Tail에서 진행하면 안되는 이유가 있는가?

[SW-H]

단방향 Linked List(싱글 연결 리스트)의 경우 각 노드의 다음 노드를 가리키는 포인터만을 가진다

-> Tail에서 push(), pop()을 하는 경우의 시간복잡도 O(N) : 예를 들어 pop()을 진행한 후에는 tail 이 기존이 가리키던 노드 그 앞 노드를 가리켜야 하는데 그러기 위해서는 head에서 부터 순차적으로 tail 바로 앞까지 가기 위해 O(N)의 시간이 걸린다. Head에서 pop()을 한 후에 head가 그 다음 노드를 가리키기 위해서는 O(1)의 시간만 필요

-> 위의 문제점은 doubly linked list를 사용하는 경우 각 노드의 앞(prev), 뒤(next)를 가리키는 포인터를 모두 가지므로 해결 가능하다.