2021년 11월

2021-11-16

자료구조(Data Structure)

사전적인 의미는 자료(Data)의 집합의 의미하며, 각 원소들이 논리적으로 정의된 규칙에 의해 나열되며 자료에 대한 처리를 효율적으로 수행할 수 있도록 자료를 구분하여 표현한 것

자료구조를 사용하면 데이터를 더 효율적으로 저장하고, 관리할 수 있으며 잘 선택된 자료구조는 실행 시간을 단축시켜주거나 메모리 용량의 절약을 이끌어 낼 수 있다.

자료구조의 선택 기준

• 자료의 처리 시간
• 자료의 크기
• 자료의 활용 빈도
• 자료의 갱신 정도
• 프로그램의 용이성

자료구조의 종류

자료구조는 크게 선형 구조와 비선형 구조로 나누어진다.

선형 구조

• 배열(Array)
• 연결 리스트(Linked List)
  • 단순 연결 리스트
  • 이중 연결 리스트
  • 원형 연결 리스트
• 덱(Deque)
• 스택(Stack)
• 큐(Queue)

비선형 구조

• 트리(Tree)
  • 일반 트리
  • 이진 트리
• 그래프(Graph)
• 방향 그래프
• 아무 방향 그래프

출처: 코인하는 프로그래머

배열(Array)

순차적(ordered)으로 데이터를 저장하는 자료구조

설명

배열은 연관된 데이터들을 하나의 그룹으로 묶어서 효율적으로 데이터들을 관리하기 위해서 사용된다.
배열에 저장되는 데이터는 순차적으로 저장되고 고유한 index 값을 가지고 있다.
하나의 배열을 구성하는 단위 데이터들을 'element', '원소'라고 부른다.
배열에 특정 원소에 접근하기 위해서는 arrayValue[index] 의 형식으로 한다.
배열의 원소를 식별하기 위해서 사용하는 index는 숫자가 아니라 문자를 사용할수도 있다. Associative Array연관배열이라고 부른다.

장점

• 바로 만들어서 활용하기가 쉽다.
• 더 복잡한 자료 구조의 기초가 될 수 있다
• 원하는 데이터를 효율적으로 탐색/가져올 수 있다
• 정렬에 용이하다

단점

• 데이터를 저장 할 수 있는 메모리 크기가 고정되어 있다
• 데이터 추가 / 삭제 방법이 비효율적이다
• 구조 재구성 시 정렬하는 방식이 비효율적이다

예제 (Example)

// Array를 선언하는 방법, a, b, c가 같다.

var a = new Array(1, 2, 3);

var b = [1, 2, 3];

var c = new Array();

c.push(1);

c.push(2);

c.push(3);

// Array와 반복문

var a = new Array(1, 2, 3);

for (var i = 0; i < a.length; i++) {

alert(a[i]); // array a의 인덱스로 i를 0부터 2까지 순차적으로 대입한 후에 alert

}

// 첫번째 인자의 형식에 따른 차이

var a = new Array(5);

alert(a); // 값이 없는 5개의 원소를 포함한 array를 생성한다. [undefined,undefined,undefined,undefined,undefined]

var b = new Array('5');

alert(b); // string object 5를 원소로 하는 array를 생성한다. ["5"]

var c = new Array(new Number(5));

alert(c); // number object 5를 원소로 하는 array를 생성한다. [5]

// 배열의 원소에 엑세스 하는 방법

var a = new Array(1, 2, 3);

alert(a[0]); // 1

alert(b[0]); // 2

alert(c[0]); // 3

// Associative array

codingeverybody = new Array();

codingeverybody['html'] = '웹문서를 만든다';

codingeverybody['css'] = 'html을 꾸며준다';

codingeverybody['javascript'] = 'html을 동적으로 제어한다';

codingeverybody['php'] = 'html을 서버측에서 동적으로 생성한다';

alert(codingeverybody['html']); // string, 웹문서를 만든다

alert(codingeverybody['css']); // string, html을 꾸며준다

codingeverybody.push(1);

codingeverybody.push(2);

alert(codingeverybody); // array, [1,2]

console.log(codingeverybody.length); // number 2

// Associative array를 자바스크립트에서는 배열이 아니라 object로 처리한다.

// codingeverybody는 array object이지만, 동시에 object이기도 하기 때문에

// html, css, javascript, php는 object codingeverybody의 원소가 아니라 property(속성)으로 사용된다.

// 그래서 위의 코드에서 codingeverybody.length 가 2가 된다.

출처: 생활코딩

2021-11-30

연결 리스트(Linked List)

각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조이다. 즉, Array List와는 다르게 엘리먼트와 엘리먼트 간의 연결(link)을 이용해서 리스트를 구현한 것을 의미한다.

• 노드: 리스트에서 연결되는 하나의 데이터 정보를 말하는데 어떠한 데이터를 담을 공간과 자신의 다음 위치를 가리킬 포인터를 노드라고 한다.

단일 연결 리스트

단일 연결 리스트는 각 노드에 자료 공간과 한 개의 포인터 공간이 있고, 각 노드의 포인터는 다음 노드를 가리킨다.

1. 데이터 삽입

리스트에 첫 번째로 담길 노드는 값을 삽입하고 다음 주소를 가리키는 포인터는 nullptr을 담아준다. 이 노드는 head와 tail을 가리키게 된다.

2. 두 번째 이후 삽입

두 번째 이후 삽입부터는 노드를 생성하고 값을 삽입한 뒤 이전 노드에 해당 노드의 주소를 가리키도록 연결을 시켜준다. 그 후 tail을 가장 마지막에 연결한 노드로 이동시켜 준다.

3. 데이터 검색 및 출력

리스트는 연결된 형태이기 때문에 앞에서부터 순차적으로 탐색을 한다. head의 위치를 변경되지 않도록 current가 노드에서부터 하나씩 다음 노드를 가리키는 포인터를 이용하여 다음 연결된 노드로 이동하여 데이터를 검색한다.

4. 데이터 삭제

데이터 삭제는 데이터 검색과 동일하게 노드를 순회하면서 다음 위치를 삭제하기 전 다다음 노드의 주소를 먼저 연결시켜준 후 삭제를 한다.

예제 코드

#include <iostream>

using namespace std;

#define MAX_LENGTH 5

// 노드 구조체

typedef struct node

{

// 생성자

node() : data(0), nextNode(nullptr) {}

// 데이터

int data;

// 다음 노드를 가리키는 포인터

node* nextNode;

}NODE;

// 리스트 구조체

typedef struct list

{

// 생성자

list() : head(nullptr), tail(nullptr) {}

// 리스트의 시작점을 나타내는 노드

node* head;

// 리스트의 끝점을 나타내는 노드

node* tail;

}LIST;

void Insert(LIST* list, int data)

{

// 노드 생성

NODE* newNode = new NODE;

newNode->data = data;

newNode->nextNode = nullptr;

// head 노드가 비어있을 경우

if (list->head == nullptr)

{

// 처음 생성한 노드를 head에 대입

list->head = newNode;

}

else

{

// 마지막 노드의 nextNode에 생성한 노드 연결

list->tail->nextNode = newNode;

}

// 가장 마지막으로 생성한 노드를 tail에 대입

list->tail = newNode;

}

void Find(LIST* list, int findData)

{

// head 노드가 비어있을 경우

if (list->head == nullptr)

{

cout << "탐색할 데이터가 없습니다." << endl;

return;

}

// head 부터 탐색할 노드, 탐색할 다음 노드 저장

NODE* curNode = list->head;

// 탐색할 값이 없을 때까지 순회

while (curNode != nullptr)

{

// 탐색하고자하는 데이터와 비교

if (curNode->data == findData)

{

cout << "탐색 값 : " << curNode->data << endl << endl;

return;

}

// 다음 위치 노드 저장

curNode = curNode->nextNode;

}

cout << "탐색 실패" << endl << endl;

}

void Delete(LIST* list)

{

// head 노드가 비어있을 경우

if (list->head == nullptr)

{

cout << "삭제할 데이터가 없습니다." << endl;

return;

}

// 시작 위치를 삭제 변수에 대입

NODE* deleteNode = list->head;

cout << "리스트 삭제 : " << "\t";

// 삭제할 노드가 더이상 없을 경우 루프 탈출

while (deleteNode != nullptr)

{

// head의 다음 위치를 head로 대입

list->head = list->head->nextNode;

// 노드 삭제

cout << deleteNode->data << "\t";

delete deleteNode;

deleteNode = nullptr;

deleteNode = list->head;

}

// 줄바꿈 처리

cout << endl << endl;

}

void Display(LIST* list)

{

// head 노드가 비어있을 경우 연산하지 않음

if (list->head == nullptr)

{

cout << "저장된 데이터가 없습니다." << endl;

return;

}

// 시작 위치를 출력 변수에 대입

NODE* printNode = list->head;

cout << "리스트 출력 : " << "\t";

// 다음 노드를 가리키는 nextNode가 비어있을 때까지 순회

while (printNode != nullptr)

{

// 데이터 출력

cout << printNode->data << "\t";

// 출력 변수에 다음 위치를 가리키도록 대입

printNode = printNode->nextNode;

}

// 줄바꿈 처리

cout << endl << endl;

}

int main()

{

// 리스트 생성

LIST* newList = new LIST;

// 노드 삽입

for (int i = 0; i < MAX_LENGTH; ++i)

{

Insert(newList, (i + 1) * 10);

}

// 리스트 출력

Display(newList);

// 리스트 검색

Find(newList, 30);

// 리스트 삭제

Delete(newList);

이중 연결 리스트(doubly linked list)

이중 연결 리스트의 구조는 단일 연결 리스트와 비슷하지만, 포인터 공간이 두 개가 있고 각각의 포인터는 앞의 노드와 뒤의 노드를 가리킨다. 그래서 탐색을 할때 해당 노드에서 앞에 노드나 뒤에 노드로 쉽게 왔다갔다 할 수 있는 장점이 있다.

1. 노드 삽입

2. 노드 삭제

예제 코드

#include<iostream>

struct Node {

int data;

Node* next, * prev;

Node() {

next = prev = NULL;

data = 0;

}

Node(int i, Node* ptr)//ptr 뒤에 추가한다.

{

data = i;

prev = ptr;

next = ptr->next;

next->prev = prev->next = this;

}

void selvDelete() {

prev->next = next;

next->prev = prev;

delete this;

}

};

struct DLinkedList {

Node *head;

Node *tail;

int count;

DLinkedList() { //생성자

count = 0;

head = new Node(); //더미를 선언해서 가지고 있게한다.

tail = new Node(); //더미를 선언해서 가지고 있게한다.

head->next = tail; //서로연결한다.

tail->prev = head;

}

~DLinkedList() {

while (head->next != tail)

head->next->selvDelete();

delete head;

delete tail;

}

void firstInsert(int i) { //head 다음에 추가한다.

new Node(i, head);

}

void endInsert(int i) { //tail 앞에 추가한다.

new Node(i, tail->prev);

}

void firstDelete() { //head 다음 노드 삭제한다.

if (head->next == tail) return;

head->next->selvDelete();

}

void endDelete() { //tail 앞에 제거한다.

if (tail->prev == head) return;

tail->prev->selvDelete();

}

void printAll() {

Node* tmp = head;

while (tmp->next != tail) {

printf("%d\n", tmp->next->data);

tmp = tmp->next;

}

}

};

원형 연결 리스트(Circular Linked List)

원형 연결리스트란 리스트의 마지막 노드의 링크가 첫 번째 노드를 가리키는 연결 리스트이다. 새 노드를 각각 머리와 꼬리에 추가하는 방식이 있다.

• 머리에 노드를 추가 시키는 방식

• 꼬리에 노드를 추가 시키는 방식

출처 : https://developer-jun.tistory.com/7, https://hijuworld.tistory.com/55, https://dudri63.github.io/2019/02/28/ds5/, https://jwlee010523.tistory.com/entry/원형-연결-리스트Circular-Linked-List