4. 선형리스트

선형 리스트

  # 원소(atom)는 논리적 레코드의 개념으로 그래프 이론에서 사용하는 노드(node)와 동일한 개념이다. 

  # 리스트(List)는 같은 종류의 자료들을 노드 단위로 구성한 집합으로, 항목(item Or field)의 순서 집합으로 볼 수 있다.

  # 리스트에는 '선형 리스트'와 '연결 리스트'의 두가지가 있다. 

  # 선형 리스트(Linear list)는 다른 말로 연접 리스트(Dense list) 또는 순서 리스트(Ordered list)라고 하며, 노드를 연속되는 기억 장소에 저장한 리스트다.

  # 선형 리스트는 각각의 노드의 위치를 색인(index) 번호를 사용하여 표시하므로 포인터가 필요 없다.

  # 이는 배열을 이용해서 구현하기 때문에 STL의 Vector와 비슷하다.

  # STL에서는 List는 이중 연결 리스트로 구현되어 있으므로 이것이 아닌 뒤쪽에 비슷한게 나온다.

  (비슷해 보이지만 원리가 완전히 다르다.)

선형 리스트의 ADT

  (ADT는 기본적인 맥락만 같으면 결국 설계하기 나름이므로 최소한만 설계하고 구현했다.)

  1. 각각의 노드에 인덱스를 사용하여 접근할 수 있어야 한다. 

  2. 원하는 위치에 노드를 추가할 수 있어야 한다.

  3. 특정 노드를 삭제할 수 있어야 한다.

  4. 리스트 전체를 순회할 수 있어야 한다.

  5. 리스트의 전체 크기를 확인할 수 있어야 한다.

C++로 구현한 선형 리스트

#pragma once
#include <assert.h>

template <typename T>
class LinearList
{
	T* arr;
	int iSize;
	int iEnd;
	int nowIndex;

private:
	//할당받은 메모리가 부족할 때 메모리를 더 할당받고 데이터를 그대로 복사.
	void moveData();

public:
	//get method
	int GetSize();
	int GetIndex();
	int GetEnd();

	//set method
	void SetIndex(int index);

	T& operator[](int index);             //인덱스로 접근, 수정이 가능.

	int addData(T data);                  //뒤에 데이터 추가
	int InsertData(int index, T data);    //중간에 데이터 삽입
	
	int DeleteData(int index);            //인덱스로 데이터 삭제
	int DeleteValue(T data);              //데이터 값으로 데이터 삭제.

	//순회용.
	T& prev();
	T& now();
	T& next();
	

public:
	LinearList();
	~LinearList();
};

//내부 함수
template <typename T>
void LinearList<T>::moveData()
{
	if (iEnd >= iSize) {
		T* backup = new T[iSize];
		for (int i = 0; i < iSize; i++) {
			backup[i] = arr[i];
		}
		arr = new T[iSize + 5];
		for (int i = 0; i < iEnd-1; i++) {
			arr[i] = backup[i];
		}
		iSize = iSize + 5;
	}
}

//생성자
template <typename T>
LinearList<T>::LinearList()
{
	arr = nullptr;
	iSize = 0;
	iEnd = 0;
	nowIndex = 0;
}

//[] 오버로딩
template <typename T>
T& LinearList<T>::operator[](int index)
{
	assert(0 <= index && index < iEnd);
	return arr[index];
}

//getMethod
template <typename T>
int LinearList<T>::GetSize()
{
	return iSize;
}

template <typename T>
int  LinearList<T>::GetIndex()
{
	return nowIndex;
}

template <typename T>
int  LinearList<T>::GetEnd()
{
	return iEnd;
}

//setMethod
template <typename T>
void  LinearList<T>::SetIndex(int index)
{
	nowIndex = index;
}

//뒤에 추가
template <typename T>
int LinearList<T>::addData(T data)
{
	moveData();

	arr[iEnd++] = data;

	return iEnd;
}

//중간에 삽입
template <typename T>
int LinearList<T>::InsertData(int index, T data)
{
	iEnd++;
	moveData();
	for (int i = iEnd; i > index; i--) {
		arr[i] = arr[i - 1];
	}

	arr[index] = data;
	
	return iEnd;
}

//index로 삭제
template <typename T>
int LinearList<T>::DeleteData(int index)
{
	iEnd--;
	for (int i = index; i < iEnd; i++) {
		arr[i] = arr[i + 1];
	}

	arr[iEnd] = 0;

	return iEnd;
}

//값으로 삭제
template <typename T>
int LinearList<T>::DeleteValue(T data)
{
	for (int i = 0; i < iEnd; ) {
		if (arr[i] == data) {
			DeleteData(i);
			i = 0;
			continue;
		}
		i++;
	}
	return iEnd;
}

//순회용.
template <typename T>
T& LinearList<T>::prev()
{
	if (nowIndex > 0) {
		return arr[--nowIndex];
	}
	return arr[0];
}


template <typename T>
T& LinearList<T>::now()
{
	return arr[nowIndex];
}


template <typename T>
T& LinearList<T>::next()
{
	if (nowIndex < iEnd) {
		return arr[nowIndex++];
	}
	return arr[iEnd-1];
}

//소멸자
template <typename T>
LinearList<T>::~LinearList()
{
	delete[] arr;
	arr = nullptr;
}

실제 사용예는 생략.