소프트웨어 개발에서 자료 관리를 위한 구조(2010, 수능)

소프트웨어 개발에서 자료 관리를 위한 구조로는 ‘배열’과 ‘연결 리스트’가 흔히 사용된다. 이 구조를 가진 저장소가 실제 컴퓨터 메모리에 구현된 위치를 ‘포인터’라고 한다.

배열은 물리적으로 연속된 저장소들을 사용한다. 배열에서는 흔히 <그림 1>과 같이 자료의 논리적 순서와 실제 저장 순서가 일치하도록 자료가 저장된다. 이때 원하는 자료의 논리적인 순서만 알면 해당 포인터 값을 계산할 수 있으므로, 바로 접근하여 읽기와 쓰기를 할 수 있다. 그런데 <그림 1>에서 자료 ‘지리’를 삭제하려면 ‘한라’를 한 칸 당겨야 하고, 가나다순에 따라 ‘소백’을 삽입하려면 ‘지리’부터 한 칸씩 밀어야 한다. 따라서 삽입하거나 삭제하는 자료의 순번이 빠를수록 나머지 자료의 재정렬 시간이 늘어난다.

 

연결 리스트는 저장될 자료와 다음에 올 자료의 포인터인 ‘다음 포인터’를 한 저장소에 함께 저장한다. 이 구조에서는 <그림 2>와 같이 ‘다음 포인터’의 정보를 담을 공간이 더 필요하지만, 이 정보에 의해 물리적 저장 위치에 상관없이 자료의 논리적 순서를 유지할 수 있다. 또한 자료의 삽입과 삭제는 ‘다음 포인터’의 내용 변경으로 가능하므로 상대적으로 간단하다. 예를 들어 <그림 2>에서 ‘소백’을 삽입하려면 빈 저장소의 ⓐ에 ‘소백’을 쓰고 ⓑ와 ⓒ에 논리적 순서에 따라 다음에 올 포인터 값인 ‘1004’와 ‘1002’를 각각 써 주면 된다. 하지만 특정 자료를 읽으려면 접근을 시작하는 포인터부터 그 자료까지 저장소들을 차례로 읽어야 하므로 자료의 논리적 순서에 따라 접근 시간에 차이가 있다.

한편 ‘다음 포인터’뿐만 아니라 논리순으로 앞에 연결된 저장소의 포인터를 하나 더 저장하는 ‘이중 연결 리스트’도 있다. 이 구조에서는 현재 포인터에서부터 앞뒤 어느 방향으로도 연결된 자료에 접근할 수 있어 연결 리스트보다 자료 접근이 용이하다.