[자료구조 복습2] Array List와 Linked List (단순, 원형,이중)

리스트에는 두가지 종류가 있다. 배열리스트와 연결리스트이다. 배열리스트는 말 그대로 '배열'을 이용하여 리스트를 구현한 것이고, 연결리스트는 포인터를 이용하여 리스트를 구현한 것이다.

 

 - 배열 리스트의 장점은 원하는 원소를 O(1) 시간으로 찾을 수 있다는 것이다. 하지만 단점은 원소의 개수가 제한되어 있다는 것, 삽입과 삭제가 까다롭다는 점이다. 아무리 탐색에서 O(1)로 효율적이더라도 , 삽입과 삭제에서 O(n)이 걸리므로 그다지 효율적이라 하지 못하겠다. 하지만 그럼에도 불구하고 배열리스트는 리스트 내의 변동 사항이 없고, 리스트의 크기가 클 때 사용하면 효율적일 것이다.

다음은 배열리스트 ADT를 C++로 구현한 것이다. 예외처리는 객체 참조자를 반환해야하는 함수에만 해주었다.

 

배열리스트 C++ 구현 

#include <iostream>
#include <cstdlib>
using namespace std;
#define MAX_ARR 20

// List ADT 구현 

class ListType {
public:
	int num;
	char name[10];
public:
	ListType() {};
	ListType(int num, const char name[]) 
	{
		this->num = num;
		strcpy(this->name, name);
	};

	bool operator ==(ListType s) { //객체 비교연산
		if (num == s.num && !strcmp(name, s.name)) return true;
		else return false;
	}
	
};

class ArrayList
{
public:
	ListType arr[MAX_ARR];
	int index = 0;

public: 
	ArrayList() {};
	void add_last(ListType item) {
		if (is_full()) {
			cout << "List 내 공간 부족" << endl;
			return;
		}
		arr[index++] = item;
	}

	void add_frist(ListType item) {
		//맨 앞에 원소 추가
		if (is_full()) {
			cout << "List 내 공간 부족" << endl;
			return;
		}
		for (int i = index-1; i >= 0; i--) {
			arr[i + 1] = arr[i];
		}
		arr[0] = item;
		index++;
	}

	void add(ListType item, int pos) {
		//pos자리에 item 추가
		if (is_full()) {
			cout << "List 내 공간 부족" << endl;
			return;
		}
		
		if (pos< 0 || pos > index) {
			cout << "pos 범위오류입니다. 다시 설정해주세요" << endl;
			return;
		}
		for (int i = index-1; i >= pos; i--) {
			arr[i + 1] = arr[i];
		}
		arr[pos] = item;
		index++;
	}

	ListType& del(int pos) {
		//pos자리의 item 삭제 
		if (index <= pos || pos < 0) {
			throw (pos); //반환값 ListType 라서 예외처리 
		}
		ListType cop = arr[pos];
		for (int i = pos; i < index - 1; i++) {
			arr[i] = arr[i + 1];
		}
		index--;
		return cop;
	}

	void clear() {
		if (is_empty()) {
			cout << "List가 비었습니다" << endl;
			return;
		}
		//리스트의 모든 원소 제거
		ListType tmp(0,"X");
		for (int i = 0; i < index; i++) {
			arr[i] = tmp;
		}
		index = 0;
	}

	void replace(int pos, ListType item) {
		if (index <= pos) {
			cout << "해당 위치에 원소가 없습니다" << endl;
		}
		//pos 위치의 원소를 item으로 바꿈
		arr[pos] = item;
	}

	bool is_in_list(ListType item) {
		for (int i = 0; i < index; i++) {
			if (arr[i] == item) { return true; }
		}
		return false;
	}

	ListType& get_entry(int pos) {
		for (int i = 0; i < index; i++) {
			if (i == pos) {
				return arr[i];
			}
		}
		cout << "해당 위치에 원소가 존재하지 않습니다." << endl;
		throw (pos); //반환값 ListType이라서 예외처리
	}

	int get_length() {
		return index;
	}

	bool is_empty() {
		if (index == 0) return true;
		else return false;
	}

	bool is_full() {
		if (index == MAX_ARR) return true;
		else return false;
	}

	void display() {
		for (int i = 0; i < index; i++) {
			cout << arr[i].num << "," << arr[i].name << endl;
		}
	}

};


int main(void) {
	ArrayList arr;
	ListType n(1, "kim");
	ListType n1(2, "lee");
	try {
		ListType cop = arr.del(2);
		cout << cop.name << endl;
	}
	catch (int expon) {
		cout << "delete 실패" << endl;
		cout << expon << " 번째 원소가 List 내에 존재하지 않습니다" << endl;
	}
}

1) 첫번째  ListType 클래스에는 리스트 내에 저장될 정보를 넣었다. 여기서는 간단하게 숫자와 이름만 적었다. 

여기서 멤버함수로 객체 연산자 '=='를 넣었는데 이는 ListType 객체 두개의 멤버변수를 비교하기 위함이다. 이는 특정 객체가 배열 안에 있는지 확인하는 함수인 'is_in_list'를 위해서 추가되었다. 두 객체의 멤버변수가 동일하면 true를 동일하지 않으면 false를 반환한다. 

 

2) 두번째 ArrayList 클래스는 ListType 배열과 함께 해당 배열의 index값을 멤버 변수로 삼고 있다. 여기서 index값은 배열 원소가 추가되면 1씩 증가하게 되어 현재 배열의 길이를 가르쳐준다.

 

 

 

단순 연결리스트 

단순연결리스트

단순 연결리스트 C++구현

#include <iostream>
using namespace std;
#define MAX_ARR 20

// 단순연결 리스트

typedef struct Node {
	int data; //data field
	Node* next; //link field
}Node; //노드 


Node* create_Node(int data) { //노드 동적 생성 
	Node* tmp = new Node;
	tmp->data = data;
	tmp->next = NULL;
	return tmp;
}


class LinkedList { //연결리스트 클래스 
private:
	Node* head_pointer; //헤드포인터 

public:
	LinkedList() {}; //생성자 
	Node* get_headPointer() { //헤드포인터 반환 
		return head_pointer;
	}
	void insert_node(Node* n, Node* before) { //선행노드 before뒤에 삽입 
		if (head_pointer == NULL) { //헤드포인터 null == list 자체가 비었음
			head_pointer = n;
			n->next = NULL;
		}
		else if (before == NULL) { //선행노드 null
			n->next = head_pointer;
			head_pointer = n;
		}
		else {
			n->next = before->next;
			before->next = n;
		}
	}


	void remove_node(Node* before, Node* removed) { //선행노드는 removed노드의 앞 
		if (before == NULL) { //선행노드가 null인경우 removed는 맨 앞 요소
			head_pointer = removed->next;
			delete removed;
		}
		else { 
			before->next = removed->next;
			delete removed;
		}
	}

	void display() { 
		Node* tmp = head_pointer;
		while (tmp != NULL) {
			cout << tmp->data << endl;
			tmp = tmp->next;

		}
	}

	Node* search(int data) { //탐색 
		Node* tmp = head_pointer;
		while(tmp!=NULL)
		{
			if (tmp->data == data)
				return tmp;
			else tmp = tmp->next;

		}
		cout << "오류" << endl;
		return tmp; //null값
	}

	
	void concat(LinkedList& list2) { //다른 연결리스트에 있는 원소들을 해당 연결리스트와 연결시키기 
		
		Node* head_pointer2;
		head_pointer2 = list2.get_headPointer(); //헤드포인터 저장
		Node* tmp = head_pointer;
		while (tmp->next != NULL) {
			tmp = tmp->next;
		}

		while (head_pointer2 != NULL) {
			tmp->next = create_Node(head_pointer2->data); //값 복사
			head_pointer2 = head_pointer2->next;
			tmp = tmp->next;
		}
	}


	void reserve() { //거꾸로 

		Node* p=head_pointer; 
		Node* q=NULL;
		Node* r=NULL;	
		while (p->next != NULL) {
			r = q;
			q = p;
			p = p->next;
			q->next = r;
		}
		head_pointer = q; //헤드포인터값 변경
	} 

	~LinkedList() { //소멸자 
		DestroyLinkedList();
	}

	void DestroyLinkedList() {
		Node* tmp = head_pointer;
		while (tmp != NULL) {
			tmp = tmp->next;
			delete head_pointer;
			head_pointer = tmp;
		}
	}

};

int main(void) {}

일단 구조는 이러하다. 구조체로 노드 데이터를 만든다. 클래스로 만들어도 무방하지만, 더 간결하기때문에 구조체로 만들었다. 구조체 내부에는 데이터 필드 (int data)와 링크 필드 (Node* next )가 있다. 데이터 필드는 해당 노드에 들어갈 '값' 즉 데이터를 저장하는 공간이도 링크필드는 연결리스트를 이루기 위해 포인터가 들어갈 공간이다.

 

 

 

원형연결리스트

 

원형연결리스트

원형연결리스트 C++구현

#include <iostream>
using namespace std;

typedef struct Node {
	int data;
	Node* next;
}Node;


Node* create_node(int data)
{
	Node* n = new Node();
	n->data = data;
	n->next = NULL;
	return n;
} //노드 동적 생성

class CircularLinkedList {
private:
	Node* head_pointer;

public:
	CircularLinkedList() {};

	void insert_frist(Node* new_node) { //처음에 삽입
		if (head_pointer == NULL) { //리스트가 비었을 때
			head_pointer = new_node; //스스로를 가리키도록 함 
			new_node->next = new_node;
		}
		else {
			new_node->next = head_pointer->next;
			head_pointer->next = new_node;
		}

	}

	void insert_last(Node* new_node) { //마지막 삽입 
		if (head_pointer == NULL) { //리스트가 비었을 때
			head_pointer = new_node;  //스스로를 가리키도록 함 
			new_node->next = new_node;
		}
		else {
			new_node->next = head_pointer->next;
			head_pointer->next = new_node;
			head_pointer = new_node;
		}
	}

	void insert_particular(Node* before, Node* new_node) {
		//before 선행노드 뒤에 삽입
		if (before == NULL) { //선행노드가 null이라면 == 리스트가 비었다면 
			new_node->next = new_node;
			head_pointer = new_node;
		}
		else{
			new_node->next = before->next;
			before->next = new_node;
		}
	}

	void display() {
		Node* tmp = head_pointer->next;
		do {

			cout << tmp->data << " ";
			tmp = tmp->next;
		} while (tmp != head_pointer->next);
		cout << endl;
	}


	void destroyCircularLinkedList() { 
		Node* tmp = head_pointer->next; //1번노드부터 마지막노드 이전까지 삭제 
		Node* tmp2;
		while (tmp!=head_pointer) { 
			tmp2 = tmp; 
			tmp = tmp->next;
			delete tmp2; //삭제
		}
		delete head_pointer; //마지막노드 (head_pointer) 삭제 
	}

	int get_length() { //리스트 길이 구하기 
		int len = 0;
		Node* tmp = head_pointer;
		do {
			len++;
			tmp = tmp->next;
		} while (tmp != head_pointer);
		return len;
	}

	~CircularLinkedList() {
		destroyCircularLinkedList();
	}


};

int main(void) {}

원형 연결리스트는 위의 그림과 같이 맨 뒷 노드와 맨 앞노드가 연결되어 있다. 그래서 헤드 포인터로 리스트를 순회할 수 있다. 원형 연결리스트의 장점은, 리스트 마지막에 새로운 노드를 삽입할 때, 단순 연결리스트보다 효율적이라는 것이다.  단순 연결리스트의 경우 리스트의 끝까지 가려면 O(n)의 시간이 걸렸다. 하지만, 원형 연결리스트 같은 경우는 리스트 마지막 노드까지 가는데에는 O(1)이 걸린다. 

 

역시 노드 타입을 정의해주는 구조체와 리스트의 몸통이 될 클래스로 구성하였다. 클래스 내부에는 Node타입 포인터인 헤드포인터가 있기때문에 클래스 내부에서 해당 헤드포인터를 수정가능하다.

 

Destroy 함수가 조금 까다로웠는데, 단순 연결리스트에서는 tmp!=NULL 일동안 계속해서 tmp의 위치를 옆으로 옮겨가며, delete 을 해주면 되었지만, 원형연결리스트는 모두 연결되어있기 때문에, 마지막 노드 -> next가 아예 유효하지 않는다. 그래서 tmp!=NULL 과같은 조건식을 써주면 에러가 난다. 그래서 내가 구현한 방법은 일단 헤드포인터는 처음에 delete 하지 않고 헤드포인터의 next 노드 , 즉 맨 첫번째 노드부터 ~ 맨 마지막-1 노드를 삭제해준다 . 때문에 여기서 while문의 조건식은 (tmp!=head_pointer)가 된다.

그리고 while문을 빠져나온 후, head_pointer를 delete 해주면 된다.

 

 

 

이중연결리스트

이중연결리스트

이중연결리스트는 제일 까다롭다. 이렇게 이중+원형 연결리스트로 쓰이는게 대부분인데, 여기서는 dummy node를 두 노드를 연결시켜서 구현했다. 즉, head 노드와 tail노드를 서로 left-right를 연결시켜 dummy node로 썼다. 

 

이중연결리스트 C++구현

#include <iostream>
using namespace std;
/*이중연결리스트 구현 */

typedef struct Node {
	int data;
	Node* left;
	Node* right;
}Node;


Node* create_Node(int data) { //노드 동적생성
	Node* n = new Node();
	n->data = data;
	n->left = NULL;
	n->right = NULL;
	return n;
}

class DoublyLinkedList {
private:
	Node* head;
	Node* tail;

public:
	DoublyLinkedList() {
		//dummy node 생성 
		head = new Node();
		tail = new Node();
		head->right = tail;
		tail->left = head;
		head->left = NULL; //초기화 
		tail->right = NULL;
	}

	void insert_particular(Node* before, Node* new_node) { 
		//선행노드 before node 뒤에 삽입 
		new_node->right = before->right;
		new_node->left = before;
		if (before->right == tail) // before가 마지막 노드라면 
			before->right->right = new_node; //left가 아니라 right를 new_node로, 
            //그래야 tail->right이 마지막 노드를 가리키게 된다
		else 
			before->right->left = new_node; //다른 노드라면 left를 new_node로
		before->right = new_node;
	}

	void insert_frist(Node* new_node) {
		//맨앞에 삽입 
		if (head->left == NULL) { //리스트가 비어있다면 head와 tail설정필요
			head->left = new_node;
			new_node->left = head;
			new_node->right = tail;
			tail->right = new_node;
		}
		else {
			head->left->left = new_node;
			new_node->right = head->left;
			head->left= new_node;
			new_node->left = head;
		}
	}

	void insert_last(Node* new_node) {
		//맨 뒤에삽입 
		if (tail->right == NULL) { //리스트가 비어있다면, head, tail설정 필요
			tail->right = new_node;
			new_node->right = tail;
			new_node->left = head;
			head->left = new_node;
		}
		else {
			tail->right->right = new_node;
			new_node->left = tail->right;
			tail->right = new_node;
			new_node->right = tail;
		}
	}

	void remove_node(Node* removed) {
		if (removed == head->left) { //맨 첫노드
			Node* tmp = removed;
			removed->right->left = head;
			head->left = removed->right;
			delete tmp;
		}
		else if (removed == tail->right) { //맨 마지막 노드 
			Node* tmp = removed;
			removed->left->right = tail;
			tail->right = removed->left;
			delete tmp;
		}

		else {
			Node* tmp = removed;
			removed->left->right = removed->right;
			removed->right->left = removed->left;
			delete tmp;
		}
	}


	~DoublyLinkedList() {
		destroyDoublyLinkedList();
	}
	void destroyDoublyLinkedList() { //소멸자
		Node* tmp = head->left;
		Node* tmp2;
		int i = 0;
		while (tmp != tail) {
			tmp2 = tmp;
			tmp = tmp->right;
			delete tmp2;
		}
	}

	void display() {
		Node* tmp = head->left;
		while (tmp != tail) {
			cout << tmp->data << " ";
			tmp = tmp->right;
		}
		cout << endl;
	}


};

int main(void) {}

이중연결리스트는 간단한 삽입 삭제의 연산의 경우에도 신경써야 할게 많다. 확실히 구현이 조금 까다롭다. 하지만 이러한 이중연결리스트는 탐색이 양방향으로 이루어지기 때문에, 효율적이다. 

나같은 경우는 dummy node를 두개의 노드를 연결시켰지만, 사실 노드 하나를 구현해서 left를 head로, right를 tail로 여기고 써도 상관 없다. 하지만 head tail 보이는 것이 더 직관적이라 판단하여 위와 같이 구현했다. 

 

신경써줘야할 부분은,

1)insert first, 가장 앞에 넣을 때 - 빈 리스트인가 아닌가 에 따라서 구현이 달라짐

2)insert last, 가장 뒤에 넣을 때  - 빈 리스트인가 아닌가에 따라서 구현이 달라지만

3)insert particular , 선행노드 before 뒤에 넣을 때 - before가 맨 마지막 노드인가 아닌가에 따라서 ,  before->right 가 새로 들어올노드를 right로 가리킬지, left로 가리킬지가 달라진다.  

 

 

 

여기까지가 자료구조의 기초 리스트들이었다.

확실히 C보다 C++이 더 어렵고 까다롭다. 객체지향+포인터이니, 가장 어려운것들만 빼놨달까.. 하지만 이렇게 하면 나중에 편하겠거니 생각하고 열심히 해보겠다..!

질문과 지적은 언제나 환영입니당