CWN(CHANGE WITH NEWS) - 자료구조, 어디까지 알고 있니? #1. 리스트, 연결리스트

리스트
리스트는 비슷한 특성을 가진 자료를 연결해 놓은 구조로 물품이나 사람의 이름 등을 일정한 순서로 적어 놓은 것으로 목록, 명단 등을 생각하면 쉽게 이해할 수 있다. 예를 들어, 1월, 2월, 3월과 같이 12개월을 늘어놓는 것, 월, 화, 수, 목, 금, 토, 일의 요일을 순서대로 나열된 구조도 일종의 리스트이다.

비슷한 특성을 가진 자료들을 모아놓았다는 면에서는 배열과 같다. 그러나 배열은 집합적인 성격이 강하고, 리스트는 연결해 놓았다는 성격이 강하다. 배열에서는 항목을 삽입하거나 삭제할 때 뒤의 항목이 그에 따라 이동하는 명령을 주어야 하지만, 리스트의 경우에는 뒤 항목이 이동하지 않고도 중간에 삽입과 삭제가 가능하다.

<삭제>

<삽입>

연결리스트
수업 시간의 과제 발표를 앞서 발표한 친구가 다음 발표할 친구를 지목하는 방식으로 수업을 해본적이 있을 것이다. 컴퓨터에서도 비슷한 사례가 있다. 연결리스트에서 자료와 다음 자료가 있는 위치를 같이 표현하는 개체 하나를 ‘노드’라고 하는데 링크정보를 따라가면, 다음 순서대로 자료를 찾을수 있게 되고, 남는 메모리 공간도 알뜰히 쓸 수 있게 된다.

이어진 자료 중간에 새로운 자료를 넣거나 불필요한 자료의 삭제가 필요할 때, 전체 자료들이 자리를 이동할 필요 없이 추가할 자료의 앞과 뒤 순서에 있는 자료에만 자료를 수정하면 된다.

이렇듯 연결리스트는 메모리 공간을 절약하고, 자료의 삽입과 삭제가 빈번할 때 사용하면 속도가 빠른 장점이 있지만 어떤 자료를 찾고자 할 때, 노드와 다음 노드를 링크로 이동하며 탐색하므로, 자료 탐색이 잦은 경우에는 속도가 느린 단점이 있다.

이렇게 이번 기사에서는 리스트와 연결리스트에 대해 알아봤다. 다음 기사에서는 연결리스트의 네가지 구현방법에 대해 알아보자.

[저작권자ⓒ CWN(CHANGE WITH NEWS). 무단전재-재배포 금지]