[자료 구조] 리스트

리스트(list)는 자료 구조의 하나로, 데이터를 일직선으로 나열한 형태를 가지고 있습니다. 데이터 추가나 삭제는 쉽지만, 원하는 데이터에 접근하려면 시간이 많이 걸립니다. - 책 알고리즘 도감

 

 

 

리스트의 개념도

 

 

리스트에서는 데이터가 메모리상의 연속된 위치에 저장되지 않아도 되며, 일반적으로 떨어진 영역에 흩어져서 저장됩니다. 또한, 각 데이터에는 '포인터(pointer)'가 있으며, 다음 데이터의 메모리 위치를 가리킵니다.

 

흩어져 저장돼 있으므로 포인터를 처음부터 순서대로 따라가야만 원하는 데이터에 접근할 수 있습니다.(이것을 순차 접근 또는 시퀀셜 엑세스(sequential access)라고 합니다.) 예를 들어, 'Red'에 접근하고 싶은 경우는 먼저 'Blue'에 접근한 다음 포인터를 따라 'Yellow'에 가야만 'Red'에 접근할 수 있습니다.

 

 

 

데이터의 추가(Blue와 Yellow사이에 Green 추가)

데이터 추가는 추가할 위치의 앞뒤 포인터를 변경만 하면 되므로 간단하다고 볼 수 있습니다. 예를 들어 'Blue'와 'Yellow' 사이에 'Green'을 추가하고 싶다면 'Green'의 포인터가 'Yellow'를 가리키도록 하고, 'Blue'의 포인터가 'Green'을 가리키도록 변경하면 됩니다.

 

 

 

 

데이터의 삭제(Yellow 삭제)

데이터 삭제도 데이터의 추가와 같이 포인터의 방향을 바꾸어주면 됩니다.

예를 들어, 'Yellow'를 삭제하는 경우를 생각해 봅시다. 이때는 'Green'의 포인터를 'Yellow'가 아닌 'Red'를 가리키도록 변경하면 삭제가 완료됩니다. 'Yellow'는 메모리에는 남지만 어디에서도 접근할 수 없으므로 일부러 삭제할 필요는 없습니다. 이후에 이 영역이 사용될 때 덮어쓰기가 되어 다시 사용할 수 있게 됩니다.

 

 

보충

리스트의 마지막 데이터는 포인터를 가지고 있지 않다고 설명했지만, 마지막 데이터의 포인터가 선두를 가리키도록 하면 리스트가 원형으로 연결됩니다. 이것을 '원형리스트' 또는 '순환 리스트'라고 합니다. 원형 리스트에는 선두나 후미라는 개념이 없습니다.

또한, 리스트에서는 각 데이터가 포인터를 하나만 가지고 있지만 두 개를 사용해서 앞뒤 데이터를 가리키도록 한 '양방향 리스트'라는 것도 있습니다. 이것은 리스트를 앞에서 뒤로는 물론, 뒤에서 앞으로도 추적할 수 있게 해서 편리합니다. 단, 양방향 리스트에서는 포인터 수가 늘어나므로 데이터 저장을 위한 영역이 많아지는 결점이 있습니다. 또한, 데이터 추가나 삭제 시에도 변경해야 할 포인터가 늘어납니다.

 

참고 - 책 알고리즘 도감