비실이의 개발 성장기

[자료구조] 선형 리스트 - 1 본문

Study memo

[자료구조] 선형 리스트 - 1

DubbingLee 2018. 5. 12. 13:02



선형 리스트란?




자료구조에서 데이터를 구조화 시키는 방식으로는 `순차 자료구조` 와 `연결 자료구조` 두가지 방식이 있다.




리스트에 나열한 데이터들이 일정한 순서를 가지고 있으면 `선형 리스트(Linear List)` 또는 `순차 리스트(Ordered List)` 라 부른다.




프로그래밍으로 선형 리스트를 표현하는 방법은 <인덱스, 데이터> 로 구성 된 `배열(Array)` 를 사용하면 된다.




선형 리스트에 저장된 데이터들이 메모리 상에 저장 될 때도 저장되는 순서가 있는데, 이 순서는 데이터가 나열 된 순서대로 정해진다.




다음과 같이 선형 리스트를 선언하면 메모리 상에는 다음과 같은 순서로 저장된다.





선형 리스트 이름 = ["홍길동", "김삿갓", "설까치"]







우리가 표현한 논리적인 순서와 실제 메모리상에 저장되는 순서가 동일하게 저장된다.






선형 리스트에서 데이터 추가




선형 리스트에서 특정 위치에 새로운 데이터를 추가하는 과정을 알아보겠다.




1번 자리에 새로운 인원을 추가하려 한다.







새로운 데이터를 추가하기 위해 맨 뒤에 새로운 데이터 공간 3을 추가했다.




그 다음 2번째 공간에 있는 데이터 부터 한칸씩 뒤로 밀어내어 1번 공간을 빈 공간으로 만든 후, 새로운 데이터를 1번에 추가했다.




여기서 확인해야 할 부분은 빈 공간을 만들기 위해 데이터가 총 몇 회 이동 했는지를 알아야 한다.




이동 횟수 공식은  `(추가하기 이전의 마지막 원소의 인덱스) - (추가할 인덱스) + 1




즉, 위 예제의 데이터 이동 횟수는 2 - 1 + 1  로,  총 2회 이동한 것을 알 수 있다.





만약, 총 100개의 데이터가 저장되어 있는 선형 리스트에서 2번째 공간에 새로운 데이터를 추가하게 된다면 




데이터 이동 횟수는  100 - 2 + 1 로,  총 99회 이동해야 한다. 




추가하려는 데이터의 위치가 선형 리스트의 맨 마지막이면 데이터를 이동 시킬 필요가 없지만(Best)




맨 앞에 추가를 해야한다면 최악의 경우(Worst)가 된다.









선형 리스트에서 데이터 삭제




선형 리스트에서 특정 위치에 데이터를 삭제하는 과정에 대해 알아보겠다.




1번 자리에 있는 데이터를 삭제하려 한다.






먼저 1번 자리에 있는 데이터를 삭제하였다.




순차 리스트는 중간에 데이터가 비어 있으면 순서가 끊기게 되므로 반드시 채워줘야 한다.




2번째 위치에 있는 데이터 부터 앞으로 한칸씩 밀어서 1번 공간을 채웠다.




데이터 추가의 경우와 마찬가지로 삭제의 경우에도 데이터의 이동 횟수를 확인해야 한다.




이동 횟수는 `(마지막 원소의 인덱스) - (삭제한 원소의 인덱스)` 로 구한다.



즉, 위의 경우에는 3 - 1 로,  총 2회 이동 한 것을 알 수 있다.




총 100개의 데이터가 저장되어 있는 선형 리스트에서 40번째 위치에 있는 데이터를 삭제한다면 




데이터의 이동 횟수는 100 - 40 으로, 데이터 이동 횟수는 60회가 된다.




삭제하려는 데이터가 선형 리스트의 맨 마지막에 위치한다면 데이터를 이동 시킬 필요가 없지만(Best)




맨 앞에 있는 데이터를 삭제 해야한다면 최악의 경우(Worst)가 된다.










선형 리스트 특징





책장에 책을 정리할 때 순서를 정하여 정리하면 나중에 어떠한 책을 찾을 때 좀 더 빠르게 찾을 수 있다.




이것은 컴퓨터 메모리에서도 동일하게 적용된다.




어떠한 데이터를 탐색하기 까지 소요되는 시간을 접근속도(access time) 라 부르며, 선형 리스트는 접근속도가 빠르다는 장점을 가지고 있다.




또, 구현하기 가장 간단한 자료구조 라는 점도 있다.




하지만 중간에 새로운 데이터를 추가하거나 삭제한다면 순서를 다시 갱신해줘야 하기 때문에 오버헤드(overhead) 가 발생한다는 단점이 있다. 





관리할 데이터가 순서가 있고 신규 데이터 추가와 삭제가 자주 발생하지 않는다면 선형 리스트로 구현하는게 좋다고 할 수 있다.







* 잘못 된 내용은 댓글로 남겨주세요.

'Study memo' 카테고리의 다른 글

[자료구조] Queue  (1) 2018.06.01
[자료구조] 선형 리스트 - 2  (0) 2018.05.19
[자료구조] 선형 리스트 - 1  (0) 2018.05.12
PaaS, SaaS, IaaS 란?  (0) 2017.06.06
0 Comments
댓글쓰기 폼