이중연결리스트 (Double Linked List) 사용법 (ft. 데이터 검색하기)

이중연결리스트 (Double Linked List) 사용법 (ft. 데이터 검색하기)

 

 

안녕하세요.

 

로스윗의 코딩캠프입니다.

 

오늘은 리스트 자료구조 중에서도

 

특히 이중 연결 리스트(Double Linked List)의 구현 및 사용방법과 데이터 접근법에 대해

 

같이 알아보겠습니다.

 

 

※ 혹시 아직 이중연결리스트에 대해서 잘 모르시는 분은 이전 포스팅을 참고해주세요 :)

 

그림으로 쉽게 이해하는 이중 연결 리스트의 특징과 장단점

그림으로 쉽게 이해하는 이중 연결 리스트의 특징과 장단점

 

 

- 이중연결 리스트, 인덱스를 통한 검색

일반 배열리스트(arraylist) 같은 경우는 인덱스를 통해 한 번에 접근이 가능했었습니다.

 

그리고 연결리스트(LinkedList)는 헤드를 통해 타고 들어가는 방식으로 접근을 했었습니다.

 

이중연결리스트(DoubleLinkedList)는 연결리스트(LinkedList)와 마찬가지로 

 

노드를 연결을 타고들어가는 방식으로 접근합니다.

 

다만 차이점이 하나 있습니다.

 

 

 

이중연결리스트 인덱스를 통해 검색하기

 

예를 들어 4개의 데이터가 들어있는 이중연결리스트(DoubleLinkedList)를 가정했을때

인덱스는 0번부터 3번까지가 있겠죠.

0번째 인덱스의 다음 인덱스인 첫번재 인덱스의 데이터를 가져오고자 한다면

앞쪽부터 next point로 이동하면서 인덱스의 위치까지 가서 데이터를 가져올 수있겠죠.

여기까지는 연결리스트(singleLinkedList)와 크게 다른점이 없어보입니다.

그런데 첫번째 데이터가 아니라 세번째 데이터를 가져온다고 가정해봅시다.

연결리스트(SingleLinkedList)는 역시 헤드부터 시작해서 세번재 데이터까지 순서대로 접근을 하겠지만

이때 이중연결리스트(DoubleLinkedList)는 테일을 가지고 있기 때문에 좀 더 효율적인 접근을 할 수 있습니다.

바로 헤드가 아닌 테일에서 부터 시작해서 Previous point로 이동해 데이터에 접근하는거죠.

 

DoubleLinkedList에서는 절반을 기준으로 해서 

 

헤드에서 가까우면 헤드를 통해서 접근하고

테일에서 가까우면 테일을 통해서 접근합니다.

 

그래서 만약에 데이터가 10개가 들어있다면 

 

최대 5번의 탐색을 통해서 데이터를 가져올 수 있게 되는 것이고

100개라면 최대 50번의 탐색을 통해 데이터를 가져올 수 있게 되는 것이죠.

 

다시 말해서 N개의 데이터가 들어있다면 최대 2분의 N번을 통해서 데이터에 접근 할 수 있는 것이죠.

 

이것을 시간복잡도로 표현하면 O(N/2)일것 같지만 

 

점근표기법의 특징에 따라 상수항인 1/2은 날려버리기 때문에

표기시에는 단순히 O(N)으로 표기하게 됩니다.

singleLinkedList와 비교해보면 시간복잡도가 O(N)으로 동일하게 표기는 되지만

실제 연산 소요시간은 절반정도로 단축되는 것을 알 수 있습니다.

 

DoubleLinkedList에서 이렇게 인덱스를 통한 접근은

가운데를 기준으로헤서 헤드부터 접근을 할 건지

 

테일에서부터 접근을 할 건지 먼저 판단 후에

노드를 타고 들어가는 방식으로 이루어지게 됩니다.

오늘 포스팅에서는 DoubleLinkedList에서 인덱스를 통해 데이터를 검색하는 방법을 알아봤습니다.

다음 포스팅에서는 DoubleLinkedList에서 데이터를 삽입하는 방법에 대해서

 

같이 한번 알아보겠습니다.

 

로스윗의 코딩캠프는 미래의 개발자 여러분을 응원합니다.

 

모두 화이팅!!

 

그림으로 쉽게 이해하는 자료구조와 알고리즘 차이

그림으로 쉽게 이해하는 자료구조와 알고리즘 차이

그림으로 쉽게 이해하는 빅오표기법 시간복잡도

그림으로 쉽게 이해하는 빅오표기법 시간복잡도