연결 리스트 Linked List

연결 리스트란 

여러 노드들이 각각 데이터와 포인터를 가지고 연결되어있는 자료구조이다. 각 노드의 포인터가 다음 노드나 이전 노드를 연결하는 역할을 한다.

 

노드라는 용어는 영어로 식물의 가지나 잎의 연결부위를 뜻하는 의미가 있는 것으로 보아, 자료구조에서의 노드가 서로 연결되어있어서 그렇게 부르는듯하다. 즉 노드는 데이터를 저장하고, 다른 데이터와 연결 지어 주는 단위 정도로 해석된다.

연결 리스트의 장점

연결 리스트는 데이터를 선형으로 저장하는 데이터 구조로서 각 노드들이 자신의 다음 노드의 주소를 가지고 있어, 배열에 비해 데이터를 추가 하거나, 삽입, 삭제가 자유롭다.

 

예를 들어 A, B, C라는 노드들이 있다고 가정해보자 A는 B의 주소를 B는 C의 주소를 가지고 있어 셋은 모두 연결되어 있다. 이 상태에서 D라는 노드를 추가하고 싶다면 C에게 D의 주소를 주면 되니 매우 간단한 일이다. 하지만 배열의 경우에는 크기가 정해져 있으니 배열 크기 이상의 데이터라면 추가하기 힘들다.

 

데이터를 삽입할 경우에도 배열은 A와 B사이에 D를 삽입하기 위해서는 B의 위치와 C의 위치를 옮겨야한다. 이러한 작업은 데이터의 수가 커질수록 부담이 되는 작업이다. 하지만 연결 리스트는 A가 D를 가리키게 하고 D가 B를 가리키게 하면 데이터의 수가 아무리 많아도 부담되지 않는다.

 

연결 리스트의 단점

연결 리스트는 연결되어있는 노드끼리만 서로의 위치를 알고 있기 때문에 배열과 같이 인덱스로 바로바로 접근할 수 없다.

즉 데이터 접근에 최대 O(n)의 시간이 소요된다.

또한 데이터를 저장하는 공간 외에 다른 노드의 주소를 저장할 공간이 필요하기 때문에 메모리 공간이 낭비된다.