Introducing. List. / 리스트 자료구조

Edit

Introducing. List.

본 스터디는 열혈강의 자료구조 - 프리렉이란 교재로 진행된다. 더욱 자세한 내용은 해당 책을 참고하기 바란다. 정말 괜찮은 책이다.

---

Introducing. List.

리스트 자료구조.

리스트 : 가장 단순한 자료구조지만 가장 널리 사용되고 기초적인 자료구조. 스택, 큐, 트리, 그래프 등 다른 여러 자료구조 구현에도 사용됨.

리스트는 자료가 Sequential하게 연결된 선형구조를 의미.

배열은 가장 쉬운 리스트 자료구조이다.

자료의 제거.

예를 들어 배열(Array)에 자료가 순서대로 정리되어 있다 생각해 보자.

|A|B|C|D|E|

여기에서 내가 C를 제거하게되면, 그 자리가 비게되고, 그걸 매꾸기위해 뒤에서부터 차례대로 한칸씩 앞으로 밀어줘야한다.

|A|B| |D|E| => |A|B|D|E| |

3번째 C자리게 계속 그냥 비어있어도 되지 않을까?
그런데 그렇게 되면 문제가 생긴다. 배열상에 공간이 있지만 그 공간이 비어있는지를 확인할 수 없어 그 자리에 자료를 추가하기가 힘들어진다.

자료의 추가.

마찬가지 예시를 보며 확인해 보자.

|A|B|C|D|E|

여기에 X를 추가하고 싶다고 하자. 하필 추가하고 싶은 곳이 C와 D 사이라면 어떨까?

|A|B|C|D|E| |
|A|B|C| |D|E|
|A|B|C|X|D|E|

먼저 한칸씩 D와 E를 밀어서 자리를 확보한다. 물론 이때 배열에 여유 공간이 있어야 한다. 없다면 추가가 불가능하다. 그리고 삽입하면 끝.

리스트 자료구조의 포인터를 이용한 구현.

리스트 자료구조는 아래 모식도와 같이 포인터를 이용하여 구현도 가능하다. 포인터로 구현시 배열과 달리 고정된 사이즈가 아니므로, 동적으로 할당하여 제한 없이 자료를 저장할 수 있다. 뿐만 아니라 중간에 있는 자료를 제거하거나 추가할 때, 포인터만 재설정하면 되므로 배열 리스트에서 처럼 중간 공백을 없애기 위한 자료의 이동도 불필요하다.

리스트의 추상 자료형.

	Operation	입력(input)	출력(Output)
리스트 생성	createList()	최대 원소 개수 n	리스트 l
리스트 삭제	deleteList()	리스트 l	N/A
원소 추가 가능 여부	isFull()	리스트 l	T/F
원소 추가	addElement()	리스트 l, 원소 위치 p, 원소 e	성공 or 실패 여부(T/F)
원소 제거	removeElement()	리스트 l, 원소 위치 p	성공 or 실패 여부(T/F)
리스트 초기화	clearList()	리스트 l	N/A
원소 갯수	getListLength()	리스트 l	원소의 개수
원소 반환	getElement()	리스트 l, 원소 위치 p	원소 e

책 저자가 객체 지향 프로그래머라 그 스타일을 쓰려고 하는지, 굳이 동적으로 배열을 할당하고 해제한다. 깊이 담긴 이유는 모르겠다. 그냥 미리 선언된 배열로 해도 되는데.

인덱스는 0번부터 시작(0-based-index)하는게 원칙이다. 따라서 원소 위치 p는 0번부터 시작해야한다.
그리고 디버깅 용도로 사용할 전체 원소를 보여주는 displayList()등이 필요할 수도 있다.