* List란?
A data structure(container) that holds a sequence of elements.
Elements are arranged linearly, in sequence.(Size is fixed or variable)
연속된 개체들을 저장하고 있는 자료구조형이다.
개체들은 나란히 배열되며 그 크기는 고정되어 있거나 가변적이다.
* ADT (Abstract Data Type)
List는 ADT이다.
ADT이란 사용자의 데이터 사용 측면에서의 사용방법만 명시되어 있고 정확한 구현방법에 대한 명시가 없는 데이터 모델을 의미한다.
List는 ADT이므로 다양한 구현방법이 존재한다.
※ Linear List
Linear List는 다음과 같이 개체(element)들이 일렬로 나열된 리스트를 의미한다.
(1) Operation
① Length(): List의 개체의 개수를 returm한다.
② Retrieve(theIndex): 주어진 index에 저장된 개체를 반환한다.
③ IndexOf(theElement): 주어진 element의 index를 반환한다.
④ Delete(theIndex): 주어진 index의 element를 삭제하고 뒤에 있는 개체들의 인덱스를 하나씩 줄여준다. 삭제된 element를 반환한다.
⑤ Insert(theIndex, theElement): 새로운 element를 theIndex에 삽입한다.
(2) Static List와 Linked List
- Static List
array를 통해 구현되며 정해진 크기를 갖는다.
Index를 통한 직접 접근이 가능하며 Insertion, deletion, resizing은 O(n)이다.
- Linked List
pointer로 element를 연결한 list이다.
구현 방식에 따라 singly-linked와 doubly-linked로 나눠지며 sorted와 unsorted로 나뉜다.
#include <iostream>
using std::cout;
using std::endl;
class List {
private:
int element[100];
int num;
public:
List() {
num = -1;
}
int Length() {
return num+1;
}
int Retrive(int theIndex) {
return element[theIndex];
}
int IndexOf(int theElements) {
for (int i = 0; i < num; i++) {
if (element[i] == theElements) {
return i;
}
}
cout << "There is no" << theElements << endl;
return -1;
}
int Delete(int theIndex) {
if (theIndex < 0 || theIndex >= num) {
cout << "The Index is out of bound!" << endl;
return -1;
}
else {
int deleteElm = element[theIndex];
for (int i = theIndex + 1; i < num; i++) {
element[i - 1] = element[i];
}
num--;
return deleteElm;
}
}
void Insert(int theIndex, int theElement) {
++num;
if (theIndex<0 || theIndex>num) {
cout << "The Index is out of bound!" << endl;
return;
}
else {
for (int i = theIndex + 1; i < num + 1; i++) {
element[i] = element[i - 1];
}
element[theIndex] = theElement;
return;
}
}
};
int main(void) {
List list;
list.Insert(0, 1);
list.Insert(1, 2);
list.Insert(2, 3);
list.Insert(3, 4);
list.Insert(4, 5);
cout << "Length of the list: "<<list.Length() << endl;
cout << "Element of the 2 index: " << list.Retrive(2) << endl;
cout << "Index of the '4': " << list.IndexOf(4) << endl;
cout << "Delete the '2': " << list.Delete(2) << endl;
cout << "Element of the 2 index: " << list.Retrive(2) << endl;
cout << "Insert the 100 in the 2" << endl;
list.Insert(2, 100);
return 0;
}
코딩을 안 한지 오래고 C언어로 할지 C++로 할지 고민이었는데 앞으로 C보다 C++을 더 많이 사용할 듯하고
객체라든지 여러 개념도 가물가물해지니 C++로 구현해보았다.
너무나 부끄러운 코드이다... 얼른 공부해서 이것 다 고쳐야겠다...
