이중연결리스트

01 Jun 2023 in csStudy

[2023.05.26 ~ 2023.06.01] 동안 공부한 이중연결리스트이다.
해당 포스트는 누구나 자료구조와 알고리즘 개정 2판을 참고하여 작성되었다.

📌 이중 연결 리스트

이중 연결 리스트(Doubly LinkedList)

이중 연결리스트는 연결리스트를 진화시킨 버전이라고 생각하면된다. 💫

이중 연결 리스트는 하나의 노드에 두개의 링크를 가지고 있다.

한 링크는 이전 노드를 가리키고, 한 링크는 다음 노드를 가리킨다.

또한, 이중 연결 리스트는 첫번째 노드 뿐만 아니라 마지막 노드의 값도 기억하고 있다.. ❗

읽기는 특정 인덱스의 값을 읽는다.

이중 연결리스트는 첫번째 노드와 마지막 노드의 값을 기억하고 있으므로 O(1)이 걸린다. 하지만 나머지 노드에 접근할 때는 O(N) 의 시간 복잡도가 걸린다.

검색은 값을 찾아 값의 인덱스를 반환한다.

검색도 마찬가지로 첫번째 노드와 마지막 노드에서는 O(1)의 시간복잡도가 걸린다.

이중 연결 리스트에서는 첫번째 노드와 마지막 노드에 삽입할때는 O(1)의 시간이 걸린다. 두 노드를 제외한 나머지 노드에서는 연결 리스트와 마찬가지로 O(N)의 시간 복잡도가 걸린다.

이중 연결 리스트에서는 첫번째 노드와 마지막 노드에 삭제할때는 O(1)의 시간이 걸린다. 두 노드를 제외한 나머지 노드에서는 연결 리스트와 마찬가지로 O(N)의 시간 복잡도가 걸린다.

이중 연결 리스트는 연결 리스트의 진화 버전으로 앞에서 뿐만 아니라 뒤에서도 접근할 수 있으며, 앞,뒤에서 삽입,삭제할때 O(1)의 시간복잡도로 해결 할 수 있다.

또한 연결 리스트는 링크가 다음 노드 정보만 가지고 있어서 이전 노드로의 이동이 어려웠다면 이중 연결리스트는 링크가 이전 노드 정보도 가지고 있어서 이전 노드로의 이동도 유연하다.

이중 연결리스는 O(1) 시간에 리스트 맨 끝에 데이터를 삽입, O(1)시간에 리스트 맨 앞에 데이터를 삭제할 수 있으므로 **큐를 위한 자료구조**이다.

✔ 큐는 데이터 끝에만 삽입, 데이터 앞에서만 삭제할 수 있는 리스트이다. (Fisrt in Fisrt Out)