단순 연결리스트 역순으로 출력하기

단순 연결 리스트를 역순으로 출력하려면 어떻게 해야 할까요

 

질문을 갑자기 받고 머리가 띵

 

그때의 상황

Q. 단순 연결리스트 역순으로 출력하려면 어떻게 해야 할까요

A. 네? 이중 연결리스트요? (내 뇌는 생각하기 싫었나 보다) 

Q. 아니 단순 연결리스트요!

A. 잠시만요. 

 

그 당시에는 문자열 역순 뭐 역순 하면 스택이 먼저 떠올라서 음 스택으로 값을 넣고 뭐 이런 식으로 하면 어떨까요.

구글링 해보니 알고리즘 문제로 종종 나오나 보다.

---

연결리스트(Linked list) 란 

연결리스트는 각 노드가 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료구조입니다.

 

연결리스트는 자료 추가와 삭제가 O(1)이라는 장점을 가지고 있지만,

특정 위치의 데이터를 검색하는데 O(n)이 걸린다는 단점도 갖고 있습니다.

한 번에 데이터 접근이 가능하지 않고 연결되어 있는 링크를 따라가야만 접근이 가능하기 때문입니다.

 

또한 연결리스트는 총 3가지의 종류가 존재합니다.

 

단일 연결 리스트

단일 연결 리스트는 각 노드에 자료 공간과 한 개의 포인터 공간이 있고, 각 노드의 포인터는 다음 노드를 가리킵니다.

 

이중 연결 리스트

이중 연결 리스트의 구조는 단일 연결 리스트와 비슷하지만, 포인터 두 개가 있고 각각의 포인터는 앞의 노드와 뒤의 노드를 가리킵니다.

 

 

원형 연결 리스트

원형 연결 리스트는 일반적인 연결 리스트에 마지막 노드와 처음 노드를 연결시켜 원형으로 만든 구조입니다.

---

위에서 네? 이중 연결리스트요? 라고 되물은 거 진짜.. 왜 그랬니

과거의 나 눈감아.. (부끄럽다)

 

그럼 여기를 잠시 봐주세요.

다시...

 

Q. 단순 연결리스트를 역순으로 출력하려면 어떻게 해야 할까요.

코드로 먼저 작성하면 이렇습니다.

아니 이게 무슨 말이야 ;

 

천천히 살펴봅시다.

먼저 next, prev, current 3개의 변수를 둡니다.

초기값으로 next와 prev에는 nil을 넣어주고 current에는 head를 넣어줍니다. 

보기 편하게 각각의 노드의 색상을 변경했습니다.

// 위 그림에서 하늘색 동그라미는 nil입니다. (자바에서는 null) 또한 각 노드의 하늘색 박스는 각 노드의 next를 나타냅니다.

초기 값을 넣어준 현재 상태는 위 그림과 같습니다.

위 코드의 while문 조건문을 봐주세요.

초기 세팅으로 current를 head라 설정했습니다.

즉 current는 초록색 노드를 가리키고 있고 nil이 아니기 때문에 조건을 만족하고 while문에 들어갑니다.

 

첫 번째 줄에 next = current.next라고 적힌 부분을 봐주세요.

next에 current의 next를 넣어줘라.

즉 초록색 노드(current)의 하늘색 부분(next)이 가리키는 것을 넣어줍니다. 

초록색 노드의 next는 오렌지색이죠.

next는 오렌지 색 노드를 가리키게 됩니다.

 

current.next에는 prev를 넣어줘라.

초록색 노드의 next는 오렌지색을 가리키고 있었는데 이걸 

prev로 변경해줍니다. 

prev는 초기값을 nil로 선언했으니 current.next가 nil이 되겠죠.

 

prev에는 current를 넣어줘라.

current가 초록색 노드를 가리키고 있으니 

prev 또한 초로색 노드를 가리키게 되겠죠.

 

current에는 next를 넣어줘라.

next가 위에서 오렌지 노드를 가리키게 변경되었으니

current 또한 오렌지 노드를 가리키게 됩니다.

여기까지 while문 1 cycle을 돈 모습입니다.

 

 

다시 while문 조건문을 봐주세요.

current가 nil이 아니니 이전과 동일한 작업을 해줍니다. (복ㅋ붙ㅋ)

 

next에 current의 next를 넣어줘라.

즉 오렌지 노드의 next가 가리키는 것을 넣어줍니다. 

오렌지 노드의 next는 빨간색이죠.

next는 빨간색 노드를 가리키게 됩니다.

 

current.next에는 prev를 넣어줘라.

오렌지 노드의 next는 빨간색을 가리키고 있었는데 이걸 

prev로 변경해줍니다. 

prev는 초록색 노드를 가리키고 있으니 current.next는 초록색을 가리키게 됩니다.

 

prev에는 current를 넣어줘라.

current가 오렌지 노드를 가리키고 있으니 

prev 또한 오렌지 노드를 가리키게 되겠죠.

 

current에는 next를 넣어줘라.

next는 빨간색 노드를 가리키고 있으니 

current 또한 빨간색 노드를 가리키게 됩니다.

여기까지 while문 2 cycle을 돈 모습입니다.

 

 

다시 while문의 조건문을 봐주세요.

current가 nil이 아니니 이전과 동일한 작업을 해줍니다. (복ㅋ붙ㅋ)

 

next에 current의 next를 넣어줘라.

즉 빨간색 노드의 next가 가리키는 것을 넣어줍니다. 

빨간색 노드의 next는 nil이죠. (하늘색 동그라미)

next는 nil이 됩니다.

 

current.next에는 prev를 넣어줘라.

빨간색 노드의 next는 nil인데 이걸

prev로 변경해줍니다. 

prev는 오렌지 노드를 가리키고 있으니 current.next는 오렌지 노드를 가리키게 됩니다.

 

prev에는 current를 넣어줘라.

current가 빨간색 노드를 가리키고 있으니 

prev 또한 빨간색 노드를 가리키게 되겠죠.

 

current에는 next를 넣어줘라.

next는 nil이니

current 또한 nil이 됩니다.

여기까지 while문 3 cycle을 돈 모습입니다.

 

 

다시 while문의 조건문을 봐주세요. 

current가 nil이죠.

while문 조건문을 만족시키지 않으며 더 이상 while문을 실행하지 않습니다.

(노드 3개로 해서 참 다행인 부분)

 

while문 아래를 봐주세요.

head = prev 

원래 head는 초록색 노드를 가리키고 있지만 역순을 위해 prev가 가리키는걸 head에 넣어줍니다.

prev는 현재 빨간색 노드를 가리키고 있으므로 head 또한 빨간색 노드를 가리키게 됩니다.

위와 같은 작업을 거치고 head부터 차례로 출력하면 역순으로 단일 연결리스트를 출력할 수 있습니다.