/ C

자료구조 정복하기 with C++ (1)리스트

자료구조 정복하기 with C++ (1)리스트

직접 코딩하면서 자료구조 공부하기

개요

자료구조와 알고리즘은 프로그램을 구성하는 가장 핵심적인 요소입니다. 프로그램 개발을 집을 짓는 것에 비유한다면 흙이나 모래, 시멘트, 목재와 같은 자재들이 바로 ‘자료구조’에 해당되고, 이러한 자재들을 이용해서 집을 짓는 것이 ‘알고리즘’에 해당됩니다. 자료구조는 가장 기본적이고 중요한 부분이기 때문에 복습하는 겸해서 직접 여러가지 자료구조를 코딩하면서 공부하기로 했습니다.

리스트

첫번째로 구현할 자료구조는 리스트(List)입니다. 먼저, 비슷한 개념인 배열은 다수의 데이터를 효율적으로 관리할 수 있는 자료구조입니다. 배열의 가장 큰 특징은 인덱스가 있다는 것입니다. 만약 인덱스를 알고 있다면 인덱스를 이용해서 데이터를 가져올 수 있습니다. 하지만 인덱스를 이용해서 데이터를 가져오려면 데이터에 대한 인덱스의 값이 고정되어야 합니다. 자연스럽게 어떤 엘리먼트가 삭제되면 삭제된 상태를 빈 공간으로 남겨둬야 합니다. 이것은 메모리의 낭비를 초래합니다. 또한 배열에 데이터가 있는지 없는지를 체크하는 로직이 필요하다는 의미이기도 합니다.

이와는 달리 리스트는 배열이 가지고 있는 인덱스라는 장점을 버리고 대신 빈틈없는 데이터의 적재라는 장점을 취한 자료구조라고 할 수 있습니다.

리스트 기능

저는 일반적인 리스트와 자동으로 정렬되는 OrderedList 두가지 리스트를 구현할 것입니다.

List

  • 값을 특정 위치, 맨끝에 추가
  • 특정 위치, 특정 값 삭제
  • 특정 위치 값 가져오기
  • 리스트 출력/결합

OrderedList

  • 값을 맨끝에 추가
  • 특정 위치, 특정 값 삭제
  • 특정 위치 값 가져오기
  • 리스트 출력/결합

List

List.h

리스트의 헤더파일

#pragma once
class List
{
private:
	int* items;								//저장될 값
	int itemCount;							//저장된 값의 개수
	int size;								//리스트의 크기

public:
	List();
	~List();
	int getItem(int index);					//특정 위치 값
	void addItem(int itm);					//맨끝 추가
	void insertItem(int index, int itm);	//특정 위치 추가
	int removeItem(int itm);				//특정 값 삭제
	int removeAt(int index);				//특정 위치 삭제
	void print();							//리스트 출력
	void concat(List& list);				//리스트 결합
};

List.cpp

리스트 소스코드

#include "List.h"
#include <iostream>

using namespace std;

//생성자
List::List()
{
	itemCount = 0;
	size = 5;
	items = new int[size];
}

//파괴자
List::~List()
{
	delete[] items;
}

//맨끝에 값 추가
void List::addItem(int itm)
{
	if (itemCount < 5)
	{
		items[itemCount] = itm;
		itemCount++;
	}
	else
	{
		int* newData = new int[size * 2];
		for (int i = 0; i < itemCount; i++)
			newData[i] = items[i];
		newData[itemCount] = itm;
		itemCount++;
		delete[] items;
		items = newData;
		size = size * 2;
	}
}

//특정 위치 값 가져오기
int List::getItem(int index)
{
	if (index < itemCount)
		return items[index];
	else
		return -99999;
}

//특정 위치에 값 추가
void List::insertItem(int index, int itm)
{
	if (index <= itemCount)
	{
		for (int i = itemCount; i >= 0; i--) {
			if (index == i)
			{
				items[i] = itm;
				break;
			}
			else
				items[i] = items[i - 1];
		}
		itemCount++;
	}
	else
		cout << "범위를 벗어난 위치입니다." << endl;
}

//리스트 출력
void List::print()
{
	for (int i = 0; i < itemCount; i++)
	{
		cout << items[i] << " ";
	}
	cout << endl;
	cout << "카운트:" << itemCount << endl;
	cout << endl;
}

//특정 위치 값 삭제
int List::removeAt(int index)
{
	int tmp, tmp2, i;
	if (index <= itemCount)
	{
		tmp = items[index];
		tmp2 = items[index + 1];
		for (i = 0; i < itemCount; i++) {
			if (index == i)
			{
				items[index] = tmp2;
				itemCount--;
				break;
			}
		}
		while (i < itemCount)
		{
			items[i] = items[i + 1];
			i++;
		}

		return tmp;

	}
	else
		return -99999;
}

//특정 값 삭제
int List::removeItem(int itm)
{
	int i, tmp;
	int value = 0;
	for (i = 0; i < itemCount; i++)
	{
		if (items[i] == itm)
		{
			tmp = i;
			items[i] = items[i + 1];
			value = 1;
			break;
		}
	}

	if (value == 0)
		return -99999;
	else
		itemCount--;

	while (i < itemCount)
	{
		items[i] = items[i + 1];
		i++;
	}
	return tmp;
}

//리스트 결합
void List::concat(List& list)
{
	int j = 0;
	for (int i = itemCount; i < itemCount + list.itemCount; i++)
	{
		items[i] = list.items[j];
		j++;
	}
	itemCount += list.itemCount;
}

OrderedList

OrderedList.h

순서리스트 헤더파일

#pragma once
class orderedList
{
	private:
		int* items;
		int itemCount;
		int size;

	public:
		orderedList();
		~orderedList();
		int getItem(int index);					//특정 위치 값
		void addItem(int itm);					//맨끝 추가
		int removeItem(int itm);				//특정 값 삭제
		int removeAt(int index);				//특정 위치 삭제
		void print();							//리스트 출력
		void concat(orderedList& oList);		//리스트 결합
};

OrderedList.cpp

순서리스트의 소스코드

#include "orderedList.h"
#include <iostream>

using namespace std;

//생성자
orderedList::orderedList()
{
	itemCount = 0;
	size = 5;
	items = new int[size];
}

//파괴자
orderedList::~orderedList()
{
	delete[] items;
}

//맨끝에 값 추가
void orderedList::addItem(int itm)
{
	int pos;
	int value = 0;

	if (itemCount < 5)
	{
		if (sizeof(items) < 1)
		{
			items[0] = itm;
			itemCount++;
		}
		else
		{
			for (pos = 0; pos < itemCount; pos++)
			{
				if (items[pos] > itm)
				{
					value = 1;
					break;
				}
			}
		}
		
		if (value == 0)
		{
			items[itemCount] = itm;
			itemCount++;
		}
		else
		{
			int count = itemCount;
			while (count > pos)
			{
				items[count] = items[count-1];
				count--;
			}
			items[pos] = itm;
			itemCount++;
		}	
	}
	else
	{
		int* newData = new int[size * 2];
		for (int i = 0; i < itemCount; i++)
			newData[i] = items[i];
		
		
		for (pos = 0; pos < itemCount; pos++)
		{
			if (items[pos] > itm)
			{
				value = 1;
				break;
			}
		}

		if (value == 0)
		{
			newData[itemCount] = itm;
		}
		else
		{
			int count = itemCount;
			while (count > pos)
			{
				newData[count] = newData[count - 1];
				count--;
			}
			newData[pos] = itm;
		}
		itemCount++;
		delete[] items;
		items = newData;
		size = size * 2;
	}
}

//특정 위치 값 가져오기
int orderedList::getItem(int index)
{
	if (index < itemCount)
		return items[index];
	else
		return -99999;
}

//순서리스트 출력
void orderedList::print()
{
	for (int i = 0; i < itemCount; i++)
	{
		cout << items[i] << " ";
	}
	cout << endl;
	cout << "카운트:" << itemCount << endl;
	cout << endl;
}

//특정 위치 값 추가
int orderedList::removeAt(int index)
{
	int tmp, tmp2, i;
	if (index <= itemCount)
	{
		tmp = items[index];
		tmp2 = items[index + 1];
		for (i = 0; i < itemCount; i++) {
			if (index == i)
			{
				items[index] = tmp2;
				itemCount--;
				break;
			}
		}
		while (i < itemCount)
		{
			items[i] = items[i + 1];
			i++;
		}

		return tmp;

	}
	else
		return -99999;
}

//특정 값 삭제
int orderedList::removeItem(int itm)
{
	int i, tmp;
	int value = 0;
	for (i = 0; i < itemCount; i++)
	{
		if (items[i] == itm)
		{
			tmp = i;
			items[i] = items[i + 1];
			value = 1;
			break;
		}
	}

	if (value == 0)
		return -99999;
	else
		itemCount--;

	while (i < itemCount)
	{
		items[i] = items[i + 1];
		i++;
	}
	return tmp;
}

//순서리스트 결합
void orderedList::concat(orderedList& oList)
{
	int pos;
	int value = 0;
	int j = 0;
	for (j = 0; j < oList.itemCount; j++)
	{
		for (pos = 0; pos < itemCount; pos++)
		{
			if (items[pos] > oList.items[j])
			{
				value = 1;
				break;
			}
		}

		if (value == 0)
		{
			items[itemCount] = oList.items[j];
		}
		else
		{
			int count = itemCount;
			while (count > pos)
			{
				items[count] = items[count - 1];
				count--;
			}
			items[pos] = oList.items[j];
		}
		itemCount++;
	}
}

결과

main.cpp

#include "List.h"
#include "orderedList.h"
#include<iostream>

using namespace std;

int main()
{
	List list1;
	List list2;

	for (int i = 0; i < 20; i++)
		list1.addItem(i);

	for (int i = 0; i < 20; i++)
		list2.addItem(i);
		
	cout << "list 클래스의 리스트" << endl << endl;
	cout << "가져온 item: " << list1.getItem(1) << endl;
	list1.print();

	cout << "0번에 3추가" << endl;
	list1.insertItem(0, 3);
	list1.print();

	cout << "삭제한 1번 위치의 item: " << list1.removeAt(1) << endl;
	list1.print();

	cout << "삭제한 99번 위치의 item: " << list1.removeAt(99) << endl;
	list1.print();

	cout << "삭제한 item 2의 위치: " << list1.removeItem(2) << endl;
	list1.print();

	cout << "list2를 list1에 추가" << endl;
	list1.concat(list2);
	list1.print();

	list1.~List();
	list2.~List();

	orderedList oList1;
	orderedList oList2;

	for (int i = 0; i < 20; i++)
		oList1.addItem(i);
	oList1.addItem(21);

	for (int i = 0; i < 20; i++)
		oList2.addItem(i);
	oList1.addItem(31);

	cout << "orderedList 클래스의 리스트" << endl << endl;
	cout << "가져온 item: " << oList1.getItem(1) << endl;
	oList1.print();

	cout << "삭제한 1번 위치의 item: " << oList1.removeAt(1) << endl;
	oList1.print();

	cout << "삭제한 item 2의 위치: " << oList1.removeItem(2) << endl;
	oList1.print();

	cout << "삭제한 item 2의 위치: " << oList1.removeItem(2) << endl;
	oList1.print();

	cout << "list2를 list1에 추가" << endl;
	oList1.concat(oList2);
	oList1.print();

	oList1.~orderedList();
	oList1.~orderedList();


	return 0;
}

리스트와 순서리스트를 작성했습니다. 결과가 잘 나옵니다!