연결리스트 시간복잡도 정리

연결된 리스트에서는 n번째 항목에 접근하는데 걸리는 시간은O(n) 이다 (파이썬 배열은 O(1))

단순연결리스트

하나의 방향으로만 연결된 구조 마지막 노드의 링크는 무조건 None이다.

원형연결리스트

마지막 노드의 링크가 첫번째 노드와 연결되어있는 리스트 구조이다.

이중연결리스트

두개의 링크를 가지고 있고 선행노드와 연결하는 prev와 후속노드와 연결하는 next를 가지고 있다.

단순연결리스트 응용: 연결된 스택

헤드포인터를top로 사용해서 삽입과 삭제가 top에서 이루어지는 구조이다.

연결리스트로 구현 스택함수의 삽입과 삭제 연산의 시간복잡도는 O(1) 이다 이는 파이썬리스트에서 용랑이 초과되면 새로운 리스트를 구현해서 때로는 시간 복잡도가 O(n)이 발생하는 경우가 있는데 링스트드 리스트로 구현한 스택에서는 이러한 일이 발생하지 않는다. 하지만

스택의 사이즈를 반환하는 함수 size는 O(n) 연결된리스트는 자기의 어디 node에 있는지 모르기 때문이다. 하지만 변수를 선언해서 잘 관리 한다면 시간복잡도를 0(1)로 만들기가 존나 가능하다.

단순연결리스트 응용 연결된 리스트

스택에서 사용했던 top를 head로 변경하면된다.

getNode(pos)의 시간복잡도는 O(n)이다 단순연결리스트는 자신의 인덱스가 없기 때문에 일일히 노드를 돌아다니면서 체크해서 반환해야하기 때문이다.
- getnode를 파이선 리스트에서 구현하면 시간복잡도는 O(1)이다.
- getEnry, replace,find 모두O(n)이다.
- insert(pos, data) 연산은 삽입하고 싶은 곳의 전 노드의 위치를 알고 있다면 O(1)하지만 모르고있다면 노드의 위치를 찾아야 하기때문에 O(n)의 시간이 걸린다.(파이썬 배열구조를 사용한다면 위치를 알고 있다고 해도 항목의 이동에 시간이 걸리기 때문에 시간복잡도는 O(n)이다.
- delete함수도 삭제하려는 노드의 위치를 알고 있다면 o(1) 모르면 O(n) 이 걸린다.

원형연결리스트의 응용: 연결된 큐

프론트와 레어가 존재하는 연결된큐 큐는 삽입 연산은 레에서 일어나고 삭제연산은 프론트에서 이러나는 선형적인 구조이다.

근데 연결된 큐에서는 마지막 노드를 tail이라는 변수로 사용해서 레어의 역할을 하게 만든다 그 이유는 front를 사용해서 구현하게 되면 마지막 노드의 위치를 알 수 없어서 o(n)의 시간이 소요되지만

원형으로 연결되어있어서 tail.link가 프론트를 가리킬 수 있다는 점에서 레어를 테일을 사용하는 것이 효휼적이다. 이렇게 하면 프론트와 테일에 O(1)의 시간을 걸려서 접근가능하다.

dequeue, enqueue 의 시간복잡도 연산 시간은 항상 O(1)이다.

이중연결리스트의 응용 연결된 덱

덱은 프론트와 레어에서 둘다 삭제와 삽입이 가능한 자료구조 이다 공통점은 여전히 중간에서 삽입과 삭제는 불가능하다는 점이다.

단일연결리스트를 이용해서 덱을 구현한다면 단점이 레어에서 삭제 연산이 일어나는 경우이다. 왜냐하면 레어의 링크는 none와 연결되는데 이렇게 삭제 연산이 일어난다면 레어가 마지막 노드를 찾아가기 위해서 순차 탐색을 거쳐서 끝까지 이동하는데 o(n)의 시간복잡도가 발생하기 때문이다.

이중연결리스트를 사용한다면 전 링크를 통해서 전 노드의 위치를 참조할 수 있기때문에 이중연결 리스트를 사용한다

전후단의 삭제의 시간 복잡도는 모두 o(1)lek