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

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

 

안녕하세요.

 

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

 

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

 

특히 이중 연결 리스트(Double Linked List)의 사용법에 대해

 

같이 알아보겠습니다.

 

 

 

 

- 이중연결리스트 데이터 삽입하기

우리가 연결리스트(SingleLinkedList)에서 데이터 삽입과 삭제를 할 때

 

next point를 변경한다고 배웠습니다.

이중연결리스트(DoubleLinkedList)에서는 이 포인트를 변경해주는 작업을

 

next point뿐만 아니라 prev point까지 신경을 써줘야 합니다.

 

 

 

이중연결리스트 모양 예시

 

그렇다면 이중연결리스트(DoubleLinkedList)에서 인덱스를 통한 데이터 삽입은 어떻게 이루어질까요?

우선 우리가 삽일할 위치의 인덱스를 찾아가는게 첫번째 일이겠죠.

 

인덱스를 검색해서 찾아가는 방법은 이전 포스팅에서 말씀드렸습니다.

 

 

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

이중 연결 리스트(Double Linked List) 구현 및 사용방법

 

 

인덱스의 위치가 헤드에서 가까우면 헤드에서부터

 

테일에서 가까우면 테일에서부터 찾아가는 방식으로 데이터를 조회한다고 했었죠.

 

아래 그림에서 보는것처럼 curr이 가리키는 위치가

 

우리가 데이터를 삽입하고자 하는 인덱스의 위치라고 생각을 해볼게요.

 

 

이중연결리스트 인덱스를 통해 데이터 삽입하기

 

 

그리고 이 위치에다가 새로 삽일 될 new Node 데이터를 넣어줄 겁니다.

 

 

 

이중연결리스트에서 new Node 삽입하기

 

new Node 데이터를 생성을 해줍니다.

 

우리가 방금 생성한 이 노란색의 new Node는

 

지금 현재 curr이 가리키고 있는 위치의 노드의 이전 노드를 자신의 이전 노드로 가지고

현재 curr이 가리키고 있는 노드는 자신의 next 노드로 가져야

 

이 노랜색의 new노드가 현재 인덱스 위치에 삽입이 될 거에요.

 

 

 

이중연결리스트 new node point 가리키기

 

 

그 다음으로 현재 curr이 가리키고 있는 이 노드와 

 

이 curr의 원래 기존의 prev였던 이 노드간의 연결을 정리해주는 작업을 한 번 더 해줘야겠죠.

그래서 이 curr 앞에 있던 이 prev노드는 next노드로 우리가 생성한 이 노란색 new Node를 가리키면 될거고,

curr노드는 prev포인트로 기존의 prev가 아닌 new Node를 가리키게 바꿔줍니다.

이렇게 하면 서로 가리키는 포인트가 정리가 됐겠죠. 

 

 

이중연결리스트 new node point 가리키기

 

그러면 최종적으로 기존의 prev와 curr사이에 

 

우리가 새로 생성한 노란색의 new Node가 삽입이 되게 됩니다.

 

 

 

데이터 삽입을 완료한 모습

 

혹시라도 중간에 연결이 잘못되거나 끊기거나 그렇게 되면

 

더이상 next나 prev로 이동을 할 수 없기 때문에

그 이후에 데이터나 그 이전의 데이터가 모두 날아가버리는 불상사가 벌어질 수도 있습니다.

그렇기 때문에 LinkedList에서는 연결을 꼼꼼하게 잘 맺어주는게 굉장히 중요하다고 볼 수 있습니다.

 

 

오늘 포스팅에서는 DoubleLinkedList에서 데이터를 삽입하는 방법을 알아봤습니다.

다음 포스팅에서는 DoubleLinkedList에서 데이터 삭제하는 방법에 대한

 

포스팅을 진행하겠습니다.

 

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

 

모두 화이팅!!

 

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

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

배열리스트와 연결리스트의 차이 (ft. 장단점 비교)

배열리스트와 연결리스트의 차이 (ft. 장단점 비교)