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

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

 

 

안녕하세요.

 

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

 

 

오늘은 리스트 자료구조 중에서도 특히 이중 연결 리스트(Double Linked List)에 대해서

 

같이 알아보겠습니다.

 

 

 

 

※혹시 아직 연결리스트, 배열리스트에 대해서 헷갈리시는 분은 이전 포스팅을 참고해주세요 :)

 

Arraylist(어레이리스트) 핵중요한 특징 3가지!!

Arraylist(어레이리스트) 핵중요한 특징 3가지!!

링크드리스트(LinkedList)의 개념과 연산 (ft. 장단점까지)

링크드리스트(LinkedList)의 개념과 연산 (ft. 장단점까지)

 

 

 

- 이중 연결 리스트 (DoubleLinkedList)

우리가 이전에 배웠던 연결리스트(LinkedList)를 그림으로 나타내면 

 

이런 모양을 가지고 있었습니다.

 

 

연결리스트 모양

 

그리고 오늘 배울 DoubleLinkedList를 그림으로 나타내면

 

이런 모양을 가지고 있습니다.

 

이중연결리스트 모양

 

 

무엇이 다른지 보이시나요?

 

이중연결리스트(DoubleLikedList)는 일반 연결리스트(LinkedList)와 뭐가 다르냐면

 

우선 연결리스트(LinkedList)는 헤드노드(Head node)를 가지고 하나씩 찾아들어가는 구조였습니다.

그런데 이중연결리스트(DoubleLinkedList)에서는 Head node와 Tail node를 각각 따로 가지고 있게 됩니다.

일반 연결리스트(LinkedList)에서는 다음 노드 가리키는 next point만를 가지고 있는데

이중연결리스트(DoubleLinkedList)에서는 그 뿐만 아니라

 

이전 노드를 가리키는 previous point도 함께 가지고 있게 됩니다.

그래서 이중연결리스트(DoubleLinkedList)라는 명칭을 사용하게 되는거죠.

 

 

 

이중연결리스트 모양

 

우선 컴퓨터에는 공짜가 없기 때문에 previous point를 하나 더 가진다는 것은

previous point를 위한 공간을 그만큼 더 사용한다는 의미겠죠.

그렇기 때문에 같은 성능에 공간만 더 차지한다면 

 

당연히 공간을 덜 쓰는 next point 하나만 쓰는 연결리스트(LinkedList)만을 사용하는게 맞을 거에요.

하지만 이중연결리스트(DoubleLinkedList)를 사용한다는 것은

 

그만큼 공간을 더 사용함에 따라서 분명한 이점이 있기 때문이겠죠.

List연산을 통해서 연결리스트(LinkedList)와 비교해서 어떤 이점이 있는지 하나씩 알아봅시다.

 

 

- 이중 연결 리스트와 연결 리스트 비교

우선 이중 연결 리스트(DoubleLinkedList)에서도 연결리스트(SingleLinkedList)에서와 마찬가지로 

 

더미노드를 사용한 구현을 하게 될 거에요.

 

그래서 이중연결리스트(DoubleLinkedList)가 처음 초기화가 됐고, 아무 데이터도 들어오지 않은 상태라면

 

아래 그림처럼 헤드 더미노드와 테일 더미노드를 하나씩 각각 가지고 있을겁니다.

그리고 헤드의 next는 테일을 가리키게 되고, Tail의 previous는 헤드를 가리키고 있겠죠.

 

 

초기모습의 이중 연결 리스트

 

 

이 이중연결리스트(DoubleLinkedList)에 실제로 데이터가 들어오게 되면 어떻게 될까요?

 

데이터 노드는 더미노드인 헤드와 더미노드인 테일 사이에 각각 위치하게 될거구요. 

 

실질적으로 가장 앞에 있게 되는 데이터 노드는 더미노드인 헤드의 바로 다음 노드가 될거구요

가장 마지막에 있는 데이터 노드는 더미노드인 테일 바로 앞에 있는 Previous 노드가 될거에요.

 

바로 아래와 그림과 같은 모양이 되겠죠.

 

 

 

데이터가 들어온 모습의 이중 연결 리스트

 

 

- 이중 연결 리스트에서 가장 뒤에 데이터를 추가하기

 

 

이중 연결 리스트에서 가장 뒤에 데이터 추가하기

 

next point만 가지고 있던 연결리스트(singleLinkedList)에서는 

 

Head부터 Tail까지 하나씩 타고 들어 간 다음에 해당 위치에서 노드를 추가하는 작업을 했었어요.

그리고 이 노드를 타고 들어가는 작업이 N번 이루어지기 O(N)의 시간복잡도를 갖는다고 말씀드렸어요.

이중연결 리스트(DoubleLinkedList)에서 우리는 어느 노드가 마지막 노드인지 한 번에 알 수 있죠.

테일 노드의 바로 이전 노드가 데이터가 들어있는 가장 마지막 노드라고 말씀드렸습니다.

 

그렇다면은 데이터를 가장 뒤에 추가해줘야 한다면은 

 

이렇게 테일 바로 앞노드에 데이터를 삽입해주면 되겠죠.

 

 

마지막에 데이터가 들어간 모습의 이중 연결 리스트

 

이중 연결 리스트(DoubleLinkedList)에서는 우리가 테일노드를 가지고 있기 때문에 

 

이 테일을 기준으로 가장 마지막 노드를 찾아서 거기다가 데이터를 추가해주기만 하면 됩니다.

 

다시 말해서 DoubleLinkedList의 데이터가 현재 100개가 들어있든,

 

1000개가 들어있든, 혹은 수백 수천개가 들어있든 간에

언제나 테일을 통해서 한 번에 가장 마지막 노드를 찾아 낼 수 있기 때문에 시간 복잡도는 O(1)을 가지게 됩니다.

1은 상수항이죠. 데이터가 몇개가 들어있든간에 항상 일정한 시간이 들어갑니다.

반대로 SingleLinkedList는 데이터가 100개면 100번 찾아들어가야 하고,

 

1000개면 1000번 찾아들어가야 되기때문에

N개 일때 N번 타고 들어가기 때문에 O(N)의 시간복잡도를 갖는다고 계속 말씀드렸습니다.

 

다음 포스팅에서는

 

이중 연결 리스트에서 인덱스를 통해 검색하는 방법에 대해서 알아보겠습니다.

 

로스윗의 코딩캠프는

 

미래의 개발자 여러분을 응원합니다.

 

모두 화이팅!!

 

개발자 여러분, 빅오표기법이 헷갈리신가요? 확실하게 알려드리겠습니다!

개발자 여러분, 빅오표기법이 헷갈리신가요? 확실하게 알려드리겠습니다!