배열과 리스트
배열(Array)
장점
- 구현이 간단함
- 임의접근: 위치를 알면 array[2]처럼 해당 자료에 빠르게 접근 가능 O(1)
단점
- 크기가 고정이기에 불필요하거나 부족한 메모리가 발생할 수 있다.
- 고정된 크기로 인해 유연한 프로그래밍이 힘들다.
- 중간 데이터의 삽입 or 삭제 발생시 데이터를 인덱스가 한칸씩 뒤로 밀리거나 앞으로 땅겨진다. (배열의 한계)
연결리스트
구성요소
- 노드(Node) : 실제 정보를 담고 있는 데이터
- 링크(Link) : 노드간의 연결을 나타내는 포인터
장점
- 메모리를 동적으로 할당하기 때문에 메모리 효율적이다.
- 중간에 데이터 삽입 or 삭제 시 비용이 적게 든다.
단점
- 구현이 복잡하다
- 순차접근: 데이터를 접근하기 위해서는 루트 노드에서 순차적으로 이동해 접근해야 한다. O(n)
단순 연결리스트 구현
#include <Iostream>
using namespace std;
class Node {
public:
int key;
int data;
Node* next;
Node()
{
key = 0;
data = 0;
next = NULL;
}
Node(int k, int d)
{
key = k;
data = d;
}
};
class SinglyLinkedList {
public:
Node* head;
SinglyLinkedList()
{
head = NULL;
}
SinglyLinkedList(Node *n)
{
head = n;
}
// 1. Check if node exists using key value
Node* nodeExists(int k)
{
Node* temp = NULL;
Node* ptr = head;
while (ptr != NULL)
{
if (ptr->key == k)
{
temp = ptr;
}
ptr = ptr->next;
}
return temp;
}
// Append a node to the List
void appendNode(Node* n) {
if (nodeExists(n->key)!=NULL) {
cout << "Node already exists width key value: " << n->key << endl;
}
else {
// 아무것도 안들어 있을 때
if (head == NULL) {
head = n;
cout << "Node Append" << endl;
}
else {
Node* ptr = head;
// ptr을 마지막 노드로 위치
while(ptr->next != NULL) {
ptr = ptr->next;
}
// 마지막 노드에 추가
ptr->next = n;
}
}
}
// 3. Prepend Node - Attach a node at the start
void prependNode(Node* n) {
if (nodeExists(n->key) != NULL) {
cout << "Node already exists width key value: " << n->key << endl;
}
else {
// 첫번째 노드인 head를 가리킨다.
n -> next = head;
// 그리고 n이 첫번째 노드가 된다.
head = n;
cout << "Node Prepended" << endl;
}
}
// 4. Insert a Node after a particular node in the List
void insertNodeAfter(int k, Node* n) {
Node* ptr = nodeExists(k);
// 조건1: k값 존재해야 함
if (ptr == NULL)
{
cout << "No node exists width key value: " << k << endl;
}
else {
// 조건2: n->key 존재 x
if (nodeExists(n->key) != NULL) {
cout << "Node already exists width key value: " << n->key << endl;
}
else {
// k값 위치에서 n노드 추가
n->next = ptr->next;
ptr->next = n;
cout << "Node Inserted" << endl;
}
}
}
// 5. Delete node by unique key
void deleteNodeByKey(int k)
{
if (head == NULL)
{
cout << "Singly Linked List already Empty." << endl;
}
// 첫번째 노드라면 그냥 지운다.
else if (head != NULL) {
if (head->key == k) {
head = head->next;
cout << "Node Unlinked with keys value: " << k << endl;
}
else
{
Node* temp = NULL;
// 이전 노드
Node* prevptr = head;
// 현재 노드
Node* currentptr = head->next;
while (currentptr != NULL)
{
// 위치 찾으면 temp에 저장
if (currentptr->key == k)
{
temp = currentptr;
currentptr = NULL;
}
else {
// 다음 노드로 이동
prevptr = prevptr->next;
currentptr = currentptr->next;
}
}
// 위치 찾았을 경우 이전 노드의 위치만 다다음 노드로 바꿔줌(제거)
if (temp != NULL)
{
prevptr->next = temp->next;
cout << "Node Unlinked with keys value : " << k << endl;
}
else
{
cout << "Node Doesn't exist with key value : " << k << endl;
}
}
}
}
// 6. update node
void updateNodeByKey(int k, int d)
{
Node* ptr = nodeExists(k);
if (ptr != NULL)
{
ptr->data = d;
cout << "Node data updated successfully" << endl;
}
else
{
cout << "Node Doesn't exist with key value : " << k << endl;
}
}
// 7. printing
void printList()
{
if (head == NULL)
{
cout << "Node Nodes in Singly Linked List";
}
else
{
cout << endl << "Singly Linked List Values : " ;
Node* temp = head;
while (temp != NULL)
{
cout<<"("<<temp->key<<","<<temp->data<<") --> ";
temp = temp->next;
}
}
}
};
int main() {
SinglyLinkedList s;
int option;
int key1, k1, data1;
do {
cout << "\nWhat operation do you want to perform? Select Option number. Enter 0 to exit." << endl;
cout << "1. appendNode()" << endl;
cout << "2. prependNode()" << endl;
cout << "3. insertNodeAfter()" << endl;
cout << "4. deleteNodeByKey()" << endl;
cout << "5. updateNodeByKey()" << endl;
cout << "6. print()" << endl;
cout << "7. Clear Screen" << endl << endl;
cin >> option;
Node* n1 = new Node();
//Node n1;
switch (option) {
case 0:
break;
case 1:
cout << "Append Node Operation \nEnter key & data of the Node to be Appended" << endl;
cin >> key1;
cin >> data1;
n1->key = key1;
n1->data = data1;
s.appendNode(n1);
//cout<<n1.key<<" = "<<n1.data<<endl;
break;
case 2:
cout << "Prepend Node Operation \nEnter key & data of the Node to be Prepended" << endl;
cin >> key1;
cin >> data1;
n1->key = key1;
n1->data = data1;
s.prependNode(n1);
break;
case 3:
cout << "Insert Node After Operation \nEnter key of existing Node after which you want to Insert this New node: " << endl;
cin >> k1;
cout << "Enter key & data of the New Node first: " << endl;
cin >> key1;
cin >> data1;
n1->key = key1;
n1->data = data1;
s.insertNodeAfter(k1, n1);
break;
case 4:
cout << "Delete Node By Key Operation - \nEnter key of the Node to be deleted: " << endl;
cin >> k1;
s.deleteNodeByKey(k1);
break;
case 5:
cout << "Update Node By Key Operation - \nEnter key & NEW data to be updated" << endl;
cin >> key1;
cin >> data1;
s.updateNodeByKey(key1, data1);
break;
case 6:
s.printList();
break;
case 7:
system("cls");
break;
default:
cout << "Enter Proper Option number " << endl;
}
} while (option != 0);
return 0;
}
연결리스트 종류
1. 단일 연결 리스트(Singly Linked List)
#include <Iostream>
using namespace std;
class Node {
public:
int key;
int data;
Node* next;
Node()
{
key = 0;
data = 0;
next = NULL;
}
Node(int k, int d)
{
key = k;
data = d;
}
};
class SinglyLinkedList {
public:
Node* head;
SinglyLinkedList()
{
head = NULL;
}
SinglyLinkedList(Node *n)
{
head = n;
}
// 1. Check if node exists using key value
Node* nodeExists(int k)
{
Node* temp = NULL;
Node* ptr = head;
while (ptr != NULL)
{
if (ptr->key == k)
{
temp = ptr;
}
ptr = ptr->next;
}
return temp;
}
// Append a node to the List
void appendNode(Node* n) {
if (nodeExists(n->key)!=NULL) {
cout << "Node already exists width key value: " << n->key << endl;
}
else {
// 아무것도 안들어 있을 때
if (head == NULL) {
head = n;
cout << "Node Append" << endl;
}
else {
Node* ptr = head;
// ptr을 마지막 노드로 위치
while(ptr->next != NULL) {
ptr = ptr->next;
}
// 마지막 노드에 추가
ptr->next = n;
}
}
}
// 3. Prepend Node - Attach a node at the start
void prependNode(Node* n) {
if (nodeExists(n->key) != NULL) {
cout << "Node already exists width key value: " << n->key << endl;
}
else {
// 첫번째 노드인 head를 가리킨다.
n -> next = head;
// 그리고 n이 첫번째 노드가 된다.
head = n;
cout << "Node Prepended" << endl;
}
}
// 4. Insert a Node after a particular node in the List
void insertNodeAfter(int k, Node* n) {
Node* ptr = nodeExists(k);
// 조건1: k값 존재해야 함
if (ptr == NULL)
{
cout << "No node exists width key value: " << k << endl;
}
else {
// 조건2: n->key 존재 x
if (nodeExists(n->key) != NULL) {
cout << "Node already exists width key value: " << n->key << endl;
}
else {
// k값 위치에서 n노드 추가
n->next = ptr->next;
ptr->next = n;
cout << "Node Inserted" << endl;
}
}
}
// 5. Delete node by unique key
void deleteNodeByKey(int k)
{
if (head == NULL)
{
cout << "Singly Linked List already Empty." << endl;
}
// 첫번째 노드라면 그냥 지운다.
else if (head != NULL) {
if (head->key == k) {
head = head->next;
cout << "Node Unlinked with keys value: " << k << endl;
}
else
{
Node* temp = NULL;
// 이전 노드
Node* prevptr = head;
// 현재 노드
Node* currentptr = head->next;
while (currentptr != NULL)
{
// 위치 찾으면 temp에 저장
if (currentptr->key == k)
{
temp = currentptr;
currentptr = NULL;
}
else {
// 다음 노드로 이동
prevptr = prevptr->next;
currentptr = currentptr->next;
}
}
// 위치 찾았을 경우 이전 노드의 위치만 다다음 노드로 바꿔줌(제거)
if (temp != NULL)
{
prevptr->next = temp->next;
cout << "Node Unlinked with keys value : " << k << endl;
}
else
{
cout << "Node Doesn't exist with key value : " << k << endl;
}
}
}
}
// 6. update node
void updateNodeByKey(int k, int d)
{
Node* ptr = nodeExists(k);
if (ptr != NULL)
{
ptr->data = d;
cout << "Node data updated successfully" << endl;
}
else
{
cout << "Node Doesn't exist with key value : " << k << endl;
}
}
// 7. printing
void printList()
{
if (head == NULL)
{
cout << "Node Nodes in Singly Linked List";
}
else
{
cout << endl << "Singly Linked List Values : " ;
Node* temp = head;
while (temp != NULL)
{
cout<<"("<<temp->key<<","<<temp->data<<") --> ";
temp = temp->next;
}
}
}
};
int main() {
SinglyLinkedList s;
int option;
int key1, k1, data1;
do {
cout << "\nWhat operation do you want to perform? Select Option number. Enter 0 to exit." << endl;
cout << "1. appendNode()" << endl;
cout << "2. prependNode()" << endl;
cout << "3. insertNodeAfter()" << endl;
cout << "4. deleteNodeByKey()" << endl;
cout << "5. updateNodeByKey()" << endl;
cout << "6. print()" << endl;
cout << "7. Clear Screen" << endl << endl;
cin >> option;
Node* n1 = new Node();
//Node n1;
switch (option) {
case 0:
break;
case 1:
cout << "Append Node Operation \nEnter key & data of the Node to be Appended" << endl;
cin >> key1;
cin >> data1;
n1->key = key1;
n1->data = data1;
s.appendNode(n1);
//cout<<n1.key<<" = "<<n1.data<<endl;
break;
case 2:
cout << "Prepend Node Operation \nEnter key & data of the Node to be Prepended" << endl;
cin >> key1;
cin >> data1;
n1->key = key1;
n1->data = data1;
s.prependNode(n1);
break;
case 3:
cout << "Insert Node After Operation \nEnter key of existing Node after which you want to Insert this New node: " << endl;
cin >> k1;
cout << "Enter key & data of the New Node first: " << endl;
cin >> key1;
cin >> data1;
n1->key = key1;
n1->data = data1;
s.insertNodeAfter(k1, n1);
break;
case 4:
cout << "Delete Node By Key Operation - \nEnter key of the Node to be deleted: " << endl;
cin >> k1;
s.deleteNodeByKey(k1);
break;
case 5:
cout << "Update Node By Key Operation - \nEnter key & NEW data to be updated" << endl;
cin >> key1;
cin >> data1;
s.updateNodeByKey(key1, data1);
break;
case 6:
s.printList();
break;
case 7:
system("cls");
break;
default:
cout << "Enter Proper Option number " << endl;
}
} while (option != 0);
return 0;
}
1. 단일 연결 리스트(Singly Linked List)
한쪽 방향으로만 연결이 된 리스트
typedef struct node
{
struct node* next;
void* data;
}Node;
2. 이중 연결 리스트(Doubly Linked List)
각 노드들이 이전과 다음노드를 가리킨다.
typedef struct node
{
struct node* next;
struct node* prev;
void* data;
}Node;
3. 다중 연결 리스트(Multiply Linked List)
각 노드가 2개 이상의 노드를 가리킨다.
typedef struct node // 노드 자료구조 선언
{
// 하나의 노드에 다중 포인터 선언
vector<struct node *> pointers;
void* data; // 노드의 데이터 구조
}Node;
4. 원형 연결 리스트(Circular Linked List)
- 리스트의 마지막 노드가 멀리있는 다른 노드(보통 첫번째 노드)를 가리키고 있는 형태
- 원형 이중 연결 리스트(circular doubly linked list)의 경우는 첫번째 노드의 prev는 마지막 노드를, 마지막 노드의 next는 첫번째 노드를 가리킨다.
참고
이론 : https://myblog.opendocs.co.kr/archives/1347
코드 : https://www.youtube.com/watch?v=mDt53JLj8sM&list=PLIY8eNdw5tW_zX3OCzX7NJ8bL1p6pWfgG&index=12
Author And Source
이 문제에 관하여(배열과 리스트), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jodmsoluth/배열과-리스트저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)