[Data Structure] CHAP 1. Linear Lists (선형리스트) - C언어 ver.

이번 챕터에서는 다양한 자료구조 중에서 Linear List에 대해 기록할 예정이다. Linear List에 대해 알려면 List가 무엇인지 먼저 알아야 하기 때문에
✅ List란 무엇인가?
✅ Linear List란 무엇인가?
이상의 두 학습목표를 가지고 학습할 것이다.

---

1. List란?

list는 일정 순서를 가지고 나열된 데이터를 의미한다. 리스트의 의미를 알았을 때 문득 리스트와 배열의 차이점이 무엇일까 하는 궁금증이 생겨서 간단하게 찾아봤다!

1-1. 배열과 리스트

결론적으로 정리를 하자면 배열의 단점을 개선하고, 배열의 특징인 인덱스의 개념을 없앤 것이 리스트라고 한다. 즉 둘은 독립적인 게 아니라는 거! 자바로 자료구조를 배웠을 때 교수님께서 list 표현방식 중 하나가 배열이라고 하셨다. 그래서 찾아본 거를 정리하자면 아래와 같다.

• 배열 : 다수의 데이터를 묶어 효율적으로 관리할 수 있는 자료구조이다. 배열의 가장 큰 특징은 인덱스가 있다는 것인데 인덱스를 알고 있다면, 이를 이용하여 원하는 데이터를 바로 꺼내올 수 있다. 하지만 배열의 요소 중 일부가 삭제된다면, 빈 공간이 생겨 메모리가 낭비되는 일이 생긴다.
• 리스트 : 리스트는 인덱스의 개념이 없는 대신 비어있는 메모리 또한 없다는 특징을 가지고있다. 중간 요소를 없애도 밀도를 촘촘하게 유지시킬 수 있지만, 요소들의 순서가 중요한 요소가 된다.

---

2. Linear Lists란?

list에 대해 간단하게 살펴보았으니, linear lists에 대해 알아보면, linear list는 해석하면 선형리스트이고, 이름 그대로 데이터를 "일렬로" 나열한 것이다.
Ex _ Months = (Jan, Feb, Mar, Apr, ... , Nov, Dec) 이런 리스트를 의미한다.

2-1. Linear List ADT

선형리스트의 개념을 간단하게 살펴보았으니, 이를 구현하기 전 ADT로 작성하는 것을 살펴보려고 한다. 사실 ADT는 쓰는 사람의 자유이다. 줄글로 설명해도 괜찮고, CHAP 0에서 설명했듯이 인간의 언어와 프로그래밍언어의 중간 수준으로 표현해도 되지만 가독성을 생각한다면 후자가 나을 거 같다.

 

아래는 C언어에서 쓰는 operation이다.

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 라고 한다.