[자료구조] Array and Linked List

Array and Linked List

 

1. Array

 

Array(배열)은 동일한 자료형의 원소들을 순서 있게 저장하는 자료구조이다.

순서 있다는 말이 배열 안의 원소들이 정렬되어야 한다는 의미가 아니다.

배열은 선형 자료구조로 값의 번호가 곧 배열의 시작점으로부터 값이 저장되어 있는 상대적인 위치가 된다.

이를 '순서 있다'라고 표현한 것이고, 각 원소들은 index를 통해 접근 가능하다.

이는 O(1), 즉 상수시간이 걸리므로 원소에 대한 접근이 빠르다는 점이 배열의 장점 중 하나이다.

 

배열은 일반적으로 정적 할당을 하게 되는데, 이 경우 처음 배열 선언시 지정한 크기만큼만 사용할 수 있다.

만약 지정한 크기보다 더 많은 원소들을 저장할 필요가 있으면,

크기가 더 큰 새로운 배열을 선언 후 기존의 원소들을 모두 복사한 후 새로운 원소들을 삽입해줘야 하는 번거로움이 있다.

이렇듯 정적인 배열은 필요로 하는 메모리의 크기에 유연하게 대처하지 못한다.

 

또한 삭제나 삽입을 할 때에도 배열의 드러나게 된다.

예를 들어 크기 10짜리 int형 배열이 있다고 가정해보자.

현재 앞에서부터 차례로 6개의 원소들이 저장되어 있는 상태이다.

 

 

이 배열의 맨앞에 새로운 원소를 삽입하고 싶으면 어떻게 해야 할까?

index 0에 추가하고자 하는 원소를 대입하면 완료될까?

그렇지 않다.

그 뒤의 원소들을 한 칸씩 뒤로 밀어줘야 한다.

 

배열 맨 앞에 새로운 원소 7을 삽입하는 경우

 

이는 O(n)의 시간이 걸리므로 상당히 효율적이지 못하다.

배열 중간의 원소를 삭제한 경우도 마찬가지로 그 뒤의 원소들을 한칸씩 당겨줘야 하므로 O(n)의 시간이 걸린다.

 

아래 코드는 배열의 주요 기능(주어진 인덱스에 대한 배열 값 출력, 주어진 인덱스의 배열 값 변경, 주어진 인덱스에 원소 삽입, 주어진 인덱스의 배열 값 삭제)을 구현한 것이다.

 

/*
20191007
Data Structure Array Implementation
*/
#include <iostream>
#include <string>
using namespace std;

class Array {
public:
	int* arr;
	int n;

	Array(int size) {
		this->n = 0;
		this->arr = new int[size];
		for (int i = 0; i < size; i++)
			arr[i] = -1;
	}

	int at(int idx) {
		if (arr[idx] == -1)
			return 0;
		else
			return arr[idx];
	}

	void set(int idx, int x) {
		if (arr[idx] == -1)
			cout << "0\n";
		else
			arr[idx] = x;
	}

	void add(int idx, int x) {
		if (arr[idx] != -1) {
			for (int i = n; i > idx; i--)
				arr[i] = arr[i - 1];
			arr[idx] = x;
		}
		else
			arr[n] = x;
		n++;
	}

	int remove(int idx) {
		if (arr[idx] == -1)
			return 0;
		else {
			int item = arr[idx];
			for (int i = idx; i < n-1; i++) {
				arr[i] = arr[i + 1];
			}
			arr[n - 1] = -1;
			n--;
			return item;
		}
	}

	void printArray() {
		if (n == 0)
			cout << "0\n";
		else {
			for (int i = 0; i < n; i++)
				cout << arr[i] << " ";
			cout << "\n";
		}
	}
};

int main() {
	int N;
	string cmds;
	Array arr(10000);
	int input;
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> cmds;
		if (cmds == "at") {
			cin >> input;
			cout << arr.at(input) << "\n";
		}
		else if (cmds == "set") {
			cin >> input;
			int data;
			cin >> data;
			arr.set(input, data);
		}
		else if (cmds == "add") {
			cin >> input;
			int data;
			cin >> data;
			arr.add(input, data);
		}
		else if (cmds == "remove") {
			cin >> input;
			cout << arr.remove(input) << "\n";
		}
		//printArray()
		else {
			arr.printArray();
		}
	}
	return 0;
}

 

2. Linked List

 

Linked List(연결 리스트)란 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료구조이다.

 

연결 리스트의 종류로는 Singly Linked List와 Doubly Linked List가 있다.

Singly Linked List는 각 노드의 포인터가 다음 노드만 가리키는 구조를 가지는 반면,

Doubly Linked List는 각 노드가 다음 노드를 가리키는 포인터와 이전 노드를 가리키는 포인터를 갖는 구조이다.

 

이 글은 Singly Linked List(단일 연결 리스트)를 기준으로 작성한다.

 

노드는 아래 사진처럼 기본적으로 데이터와 포인터로 이루어져 있다.

보통 구조체나 클래스로 구현한다.

 

노드

 

단일 연결 리스트에서의 삽입과 삭제는 배열과 비교했을 때 비교적 간편하다.

특히 연결 리스트의 맨 앞이나 맨 뒤에 새로운 노드를 삽입하거나,

맨 앞이나 맨 뒤의 노드를 삭제할 경우 O(1)의 시간이 걸리게 된다.

 

반면 검색 기능의 경우 배열처럼 인덱스를 통한 참조가 불가능하기 때문에

직접 원하는 데이터를 저장하는 노드를 찾아야 하기 때문에 O(n)이 시간이 걸리는 단점이 있다.

 

/*
20191007
Data Structure Singly Linked List Implementaion
*/
#include <iostream>
#include <string>
using namespace std;

class Node {
public:
	int data;
	Node*next;

	Node(int x) {
		this->data = x;
		this->next = NULL;
	}
};

class Linkedlist {
public:
	Node * head;
	Node * tail;
	int n;

	//더미 노드 활용 X
	Linkedlist() {
		this->head = NULL;
		this->tail = NULL;
		this->n = 0;
	}

	void addFront(int x) {
		Node * cur = new Node(x);
		if (n == 0) {
			head = cur;
			tail = cur;
		}
		else {
			Node*tmp = head;
			head = cur;
			head->next = tmp;
		}
		n++;
	}

	int removeFront() {
		if (n == 0)
			return -1;
		else {
			Node*temp = head;
			int item = head->data;
			head = head->next;
			n--;
			delete temp;
			return item;
		}
	}

	int front() {
		if (n == 0)
			return -1;
		else {
			int item = head->data;
			return item;
		}
	}

	int empty() {
		if (n == 0)
			return 1;
		else
			return 0;
	}

	int removeBack() {
		if (n == 0)
			return -1;
		else {
			int item = tail->data;
			n--;
			Node*tmp = head;
			Node*ptr = tmp;
			while (tmp->next != NULL) {
				ptr = tmp;
				tmp = tmp->next;
			}
			ptr->next = tmp->next;
			tail = ptr;
			delete tmp;
			return item;
		}
	}

	void showList() {
		if (n == 0)
			cout << "-1\n";
		else {
			Node*temp = head;
			while (temp != NULL) {
				cout << temp->data << " ";
				temp = temp->next;
			}
			delete temp;
			cout << "\n";
		}
	}

	void addBack(int x) {
		Node*cur = new Node(x);
		if (head == NULL) {
			head = cur;
			tail = cur;
		}
		else {
			tail->next = cur;
			tail = tail->next;
		}
		n++;
	}
};

	int main() {
		int N;
		cin >> N;
		Linkedlist list;
		string cmds;

		for (int i = 0; i < N; i++) {
			cin >> cmds;
			if (cmds == "addFront") {
				int input;
				cin >> input;
				list.addFront(input);
			}
			else if (cmds == "removeFront")
				cout << list.removeFront() << "\n";
			else if (cmds == "front")
				cout << list.front() << "\n";
			else if (cmds == "empty")
				cout << list.empty() << "\n";
			else if (cmds == "showList")
				list.showList();
			else if (cmds == "addBack") {
				int input;
				cin >> input;
				list.addBack(input);
			}
			else
				cout << list.removeBack() << "\n";
		}
	}