너무 쉬운 자료구조 - 리스트

비전공자들은(나를 포함해서) 자료구조가 너무 어렵다. 그래도 꾸역꾸역 외우고 간단하게라도 이해라는 걸 해야 정보처리기사를 준비하던 할 게 아닌가. 중요한 자료구조에 대해 몇 가지 아주 쉬운 개념 이해를 하고자 한다.

 

리스트는 데이터를 일렬로 나열한 형태이다. 특징은 데이터 추가나 삭제는 쉬운데 데이터접근에 시간이 걸린다는 것이다.

각 데이터에는 포인터라는 것이 있고 이는 다음 데이터의 메모리 위치를 나타낸다.

즉 아래와 같이 표현 할 수 있다.

 

자료A (pointer)----->자료B(pointer)----->자료C

 

위와 같이 다음 자료의 메모리 주소를 갖고 있으므로 자료들이 연속적으로 메모리에 배치 되지 않아도 된다.

다음 데이터의 주소를 알고 있으므로 주소를 따라가면 찾을 수 있다.

 

메모리가 아래와 같이 생겼다면 아래와 같이 배치될 수 있다.

즉 메모리 상에서 위치가 띄엄 띄엄 있어도 다음 자료의 메모리주소를 포인트가 알고 있으므로 찾아가는데 문제없다.

 

그런데 저렇게 생기다 보니, 자료를 찾으려면 처음부터 포인트를 따라가며 자료를 찾아야 한다.(순차접근 = Sequential Access)

C를 찾아가려면 A부터 B를 거쳐 C를 찾아가야 한다. 

추가는 추가할 앞 뒤의 포인터를 변경한다.

만약 자료A 뒤에 자료D를 추가하고 싶으면 자료A의 포인터를 자료B가 아닌 자료D를 가리키게 하고 자료D의 포인터로 자료B를 가리키게 하면 된다. 아래 그림처럼 말이다.

 

자료A(pointer)----->자료D(pointer)----->자료B(pointer)----->자료C

 

그럼 삭제는 어떻게 할까? 앞에 있는 자료의 포인터가 가르키는 부분을 바꾸면 된다.

자료B를 삭제해보자.

 

 

위의 그림처럼 자료B를 찾아갈 수 있는 방법이 사라졌으므로 자료B는 나중에 덮어쓰기가 된다.

리스트를 사용하여 자료를 저장했을 때 자료처리에 걸리는 시간을 빅오표기로 나타내면 다음과 같다.

데이터수가 n개라면 검색할 때 앞에서 부터 하나씩 따라가야 하므로 O(n)의 시간이 걸린다.

추가, 삭제할 때는 포인터만 변경하면 되므로 n과 상관없이 일정하다. 즉 O(1)이 된다.