컴언

리스트 (List) - 2. LinkedList 구현

자료구조

이전 편에서 array 를 이용한 List 구현 방법인 ArrayList 에 대해 살펴보았는데요, 오늘은 다른 방법인 Linked List 에 대해 알아봅시다. 한국말로는 연결 리스트라고 합니다.


연결리스트란?

연결 리스트의 가장 좋은 비유 대상은 석탄 열차 아닌가 싶습니다. 요즘은 이런 기차가 많이 없어져서 모르는 분도 계실 것 같아 사진을 가져왔는데요.


석탄 열차는 맨 앞에 기사님이 타고 계신 차가 있고, 그 뒤로 석탄을 실은 차들이 서로에게 연결 되는 구조입니다. 연결 리스트에서는 데이터들이 저장되는 공간을 Node 라고 하고요, 기차의 한 량을 Node 라고 생각하시면 되겠습니다. 각 Node 는 데이터를 담아두는 data (석탄) 와 다음 Node 를 가리키는 next 포인터 (연결 고리)를 가지고 있습니다. 만약 석탄 차 하나를 더추가하려면 (add) 맨 뒤에 고리로 연결을 시키면 됩니다. 중간의 석탄 차 하나를 빼고 싶다면(remove) 빼고 싶은 차의 연결을 풀고 그 앞차와 뒷차를 다시 연결시키면 되고요.


N 개의 항목이 있는 연결 리스트의 예

비유로 알아봤으니 이제 진지한 정의를 해보겠습니다. 위 그림에서 연결 리스트는 리스트의 맨 앞(item 1)을 가리킵니다. 항목을 포함하고 있는 각각의 사각형들은 노드(node) 입니다. 노드는 크게 두 부분으로 이루어져있는데, 데이터를 담는 data 필드와 다음 노드를 가리키는 next 포인터입니다. 이 next 포인터들 덕분에 각각의 노드가 연결되는 것이라서 연결 리스트라고 이름 붙여진 것입니다. 각 노드의 next 포인터는 다음 노드를 가리키고요, 예외적으로 마지막 노드의 next 포인터는 다음 노드가 없으므로 null 을 가리키게 됩니다.




Node: 사실상 연결 리스트를 이루는 item

연결 리스트를 구현의 첫 단계는 Node를 구현하는 것입니다. Listnode 라는 Node를 아래에서 구현해보도록 하겠습니다.

Listnode 클래스에는 두 가지 필드가 있어야 합니다. data 필드와 next 필드이고요, 이 필드의 get/set 메소드들도 구현해야합니다. 

그리고 next 필드에 대해 첨언을 하자면, next 포인터는 다음 노드 그 자체인 Listnode 클래스를 가리키는 것이지 그 노드의 data 나 next 필드를 가리키는 것이 절대 아닙니다. 이 정도만 유의해두고 아래 실제 Java 구현을 보시죠~

<<< Listnode 구현 >>>


이제 노드도 구현을 해봤는데요, 이 노드들이 모여 어떻게 연결 리스트를 이루는지 알아보겠습니다. 우선 Listnode 하나를 만들고 시작합니다.


1. 이라는 Listnode 를 선언.

Reference 타입이기 때문에 아직 아무것도 가리키고 있지 않는 상태입니다.


데이터는 "ant", next 포인터는 null 인 Listnode 를 메모리에 할당, l 이 가리키게 함.

우리 LinkedList 의 첫번째 item 입니다.


"bat" 데이터를 가진 Listnode 를 생성하고, 

l 이 가리키고 있는 "ant" 노드의 next (다음 노드)로 "bat" 노드를 가리키게 함. 

"bat" 노드는 우리 연결 리스트의 두 번째 item이 되었습니다.


이렇게 두 개의 항목을 가진 연결 리스트를 만들어 보았습니다. 참 쉽죠? 

문제! 만약 두번째 노드의 data 를 "cat" 으로 변경하고 싶다면 어떻게 해야할까요? 두번째 노드.setData("cat") 일텐데... 문제는 "두번째 노드"를 어떻게 표현하느냐, 즉 두번째 노드의 reference 가 무엇이냐에 있을 것입니다. 

-> 연결 리스트에서 특정 노드의 reference 를 얻기 위해서는 무조건 처음 노드에서부터 시작해 원하는 노드까지 next 를 따라가며 찾아야 합니다. 


이 경우에는 다행히 두번째 노드라서 

l.getNext().setData("cat");

 으로 해결이 가능하지만, 


100번째 노드라면 

l.getNext().getNext().getNext()...반복...getNext().getNext() 

와 같이 알아낼 수 밖에 없습니다.


이건 좀 이따가 index 로 아이템 get 해오는 메소드 구현할 때 다시 이야기해보도록 하죠. ㅎㅎ


연결 리스트의 실제 구현 (Java)

노드도 구현했고, 노드가 모여 어떻게 연결 리스트를 이루는 지도 알아봤으니 아래에서 연결 리스트를 구현해보도록 하겠습니다.

연결 리스트의 연산 종류


1. add 메소드

기본적인 항목 추가인데요, 이미 연결 리스트가 주어져 있고 그 리스트에 n 이라는 임의의 Listnode 가 있다고 가정합시다. 또한 새 노드의 data 가 될 newdat 도 있다고 가정했을 때, n 이라는 노드 뒤에 새 노드를 어떻게 추가할지를 설명해보겠습니다.

연결 리스트에서 항목 추가의 메커니즘은 사실 간단하게 정리될 수 있습니다.

1. 주어진 데이터를 가진 새 노드를 만든다.

2. "연결!"

a. 새 노드의 next 포인터가 n 노드의 next 가 가리키고 있던 노드를 가리키게 한다.

b. n의 next 포인터가 새 노드를 가리키게 한다. 


이 과정을 그림으로 아래에 나타내보겠습니다.

1단계.  예제로 쓸 연결 리스트입니다. n 노드와 추가할 새로운 노드 보이시죠?

새로운 노드를 n 노드 뒤에 바로 추가할 겁니다.


2-a 단계. 추가할 노드의 다음 노드(next)를 정해줘야죠.

이제 n 노드의 next가 추가할 노드를 가리키게 해야합니다.

왜? 간단하죠!! n 노드 다음에 추가하는 노드이니깐요!


2-b 단계. ㅎㅎ 이렇게 해서 새 노드를 추가시켰습니다.

위의 과정에서 보셨듯이 연결 리스트에서 항목을 추가할 때는 노드 사이의 연결 순서를 알맞게 변경해주는 게 중요합니다. 반대로 항목을 삭제할 때도 고아가 되는 노드가 없게 순서를 잘 맞춰줘야겠죠. 이 과정을 이번에는 실제 Java 코드로 나타내면 아래와 같습니다. 

<<< 위 과정의 Java 코드 >>>

연결 리스트에서 add() 할 때의 시간 복잡도는 뭘까요? 1단계는 단순 메모리 할당이니깐 O(1), 2,3 단계에서는 결국 각 노드들의 필드들을 변경하는 거니깐 O(1)! 그래서 결국 시간 복잡도는 O(1)이라고 할 수있습니다. 다시 말해서 리스트에 수 만개의 항목이 있든, 한 개밖에 없든 간에 add() 에 걸리는 시간은 똑같다는 것이죠 ㅎㅎ

2. remove 메소드