이번 챕터에서는 다양한 자료구조 중에서 Linear List에 대해 기록할 예정이다. Linear List에 대해 알려면 List가 무엇인지 먼저 알아야 하기 때문에
✅ List란 무엇인가?
✅ Linear List란 무엇인가?
이상의 두 학습목표를 가지고 학습할 것이다.
1. List란?
list는 일정 순서를 가지고 나열된 데이터를 의미한다. 리스트의 의미를 알았을 때 문득
리스트와 배열의 차이점이 무엇일까 하는 궁금증이 생겨서 간단하게 찾아봤다!
1-1. 배열과 리스트
결론적으로 정리를 하자면 배열의 단점을 개선하고, 배열의 특징인 인덱스의 개념을 없앤 것이 리스트라고 한다.
- 배열 : 다수의 데이터를 묶어 효율적으로 관리할 수 있는 자료구조이다. 배열의 가장 큰 특징은 인덱스가 있다는 것인데 인덱스를 알고 있다면, 이를 이용하여 원하는 데이터를 바로 꺼내올 수 있다. 하지만 배열의 요소 중 일부가 삭제된다면, 빈 공간이 생겨 메모리가 낭비되는 일이 생긴다.
이런 배열의 문제점을 해결하기 위해 나온 것이 바로 리스트이다.
- 리스트 : 리스트는 인덱스의 개념이 없는 대신 비어있는 메모리 또한 없다는 특징을 가지고있다. 중간 요소를 없애도 밀도를 촘촘하게 유지시킬 수 있지만, 요소들의 순서가 중요한 요소가 된다.
뭐 어쨋든 리스트는 요소의 순서가 중요하다는 게 핵심이다 😊🌟
2. Linear Lists란?
list에 대해 간단하게 살펴보았으니, linear lists에 대해 알아보면, linear list는 해석하면 선형리스트이고, 이름 그대로 데이터를 "일렬로" 나열한 것이다.
예를 들면 )
Months = (Jan, Feb, Mar, Apr, ... , Nov, Dec) 이런 리스트를 의미한다.
2-1. Linear List ADT
선형리스트의 개념을 간단하게 살펴보았으니, 이를 구현하기 전 ADT로 작성하는 것을 살펴보려고 한다. 사실 ADT는 쓰는 사람의 자유이다. 줄글로 설명해도 괜찮고, CHAP 0에서 설명했듯이 인간의 언어와 프로그래밍언어의 중간 수준으로 표현해도 괜찮다. 하지만 가독성 측면에서는 후자가 더 좋으므로 웬만하면 후자로 쓰도록 하자!
AbstractDataType LinearList
{
instances
ordered finite collections of zero or more elements
operations
IsEmpty(): return true if the list is empty, false otherwise
Length(): retur the list size (number of elements in the list)
Retrieve(index): return the indexth element of the list
IndexOf(x): return the index of the first occurrence of x in the list, return -1 if x is not in the list
Delete(index): remove and return the indexth element, elements with higher index have their index reduced by 1
Insert(theIndex, x): insert x as the indexth element, elements with theIndex >= index have their index increased by 1
}ADT로 표현하면 위와 같이 쓸 수 있다.
- instances (objects) : 이 부분은 바꿀 수 없다. 즉 수정이 안 된다. 이 부분을 수정하게 되면 기능이 달라지므로, 새로운 자료구조를 생성하는 것이 된다.
- operations (functions) : 이 부분의 함수명을 Mandatory Operation 이라고 부른다. ADT에서 해당 자료구조를 구현할 때 꼭 쓰라는 함수이다. 여기에 써있는 함수를 이용해 구현하며, 이 외에 다른 함수를 추가해도 된다. 참고로 추가하는 함수는 Additional Operations 라고 한다.
이렇게 list와 linear lists에 대해 알아보았다!
2023/1/30 기록 완 🎶✌️
