대학교 중간 시험이 얼마안남았다보니 현재 동아리 팀원들과 함께 하고있는 프로젝트와 같이 시험공부를 병행하게 되어 시간이 부족하다고 느껴지고있다.
이번 중간 시험 자료구조에서 연결리스트에 대한 내용이 들어가있다. 그래서 연결리스트에 대해 공부를 하였다.
연결리스트에 대해 들어가기전 우선 배열과 순차리스트 들에 대해 알아보자 .
배열
<그림 출처 : https://wikidocs.net/206 위키독스 -배열 >
배열은 같은 타입의 변수들로 이루어진 유한 집합이다.
배열은 크기가 정해져 있으며, 인덱스를 활용하여 값을 조회하기에 값을 빠르게 조회할수 있는 장점이있으나 배열안의 요소를 삭제를 하더라도 요소만 삭제가 되지 공간이 삭제가 되지않기에 메모리의 낭비문제가 있다.
순차리스트
데이터들을 순서대로 메모리에 연속하여 저장하는 배열을 활용하기에 조회속도가 빠르지만 삽입 연산이 나 삭제 연산후에 연속적인 물리주소를유지하기 위해 원소들을 이동시키는 추가작업과 시간소요가 걸리게된다.
연결 리스트
리스트를 연결 자료구조로 표현한 리스트, 연결 방식에 따라 단방향(단순)연결리스트 ,양방향 연결리스트 , 원형연결리스트 들로 나타낼수 있다.
연결 자료구조
자료의 논린적인 순서와 물리적인 순서가 불일치하다
각 원소에 저장되어 있는 다음 다음원소의 주소에의해 순서가 연결되는 방식이다. 물리적인 순서에 맞추기위한 오버헤드가 발생하지가 않게 되고, 크기 변경이 유연하고 더 효율적으로 메모리가 사용이가능하다.
연결리스트의 노드
연결리스트의 노드는 연결 자료구조에서 하나의 원소를 표현하기 위한 단위구조이다 . <원소 , 주소>의 구조를 가지고 있다.
data 필드: 원소의 값이 저장이 된다.
link 필드: 다음 노드의 주소를 저장한다. 포인터 변수를 사용하여 주소값을 저장한다.
단순 연결리스트
단순연결리스트는 어떻게 사용할수있을까
리스트 삽입
- 삽입할 노드를 준비한다 .
- 새 노드의 데이터필드에 값을 저장한다.
- 새 노드의 링크값을 지정한다
- 리스트의 앞노드에 새로운 노드를 연결한다.
리스트 삭제
리스트를 삽입했으면 삭제를 하는 방법도 알아줄필요가있다.
1. 삭제할 노드의 앞노드를 찾는다
3. 앞노드에 삭제할 노드의 링크필드값을 저장한다.
3. 삭제한 노드의 앞 노드와 삭제한 노드의 다음노드를 연결해준다.
예시를 알아보자
이렇게 월 수 금 일 노드가 있다. 나는 '수'노드를 삭제하고 싶다.
그러기위해서는 '수' 노드인 앞인 '월'노드에 '수'노드의 다음 노드인 '금'노드를 연결해주어야한다. 이후 '수' 노드를 삭제해준다.
단순연결리스트 c++ 구현
연결리스트에 대해 알아보았으니 한번 c++ 에서 구현해보았다.
#include <bits/stdc++.h>
using namespace std;
template <typename T>
class SingleLinkedList // 단방향 연결리스트 클래스
{
private:
struct Node
{
T data; //데이터 필드
Node* next; //링크 필드
};
Node* head;
Node* tail;
int size;// 리스트 사이즈
public:
SingleLinkedList() //생성자
{
head = nullptr;
tail = nullptr;
size = 0;
}
void PushFront(T data) //앞으로 삽입하는 방식
{
Node* newNode = new Node;
newNode->data = data;
newNode->next = nullptr;
if (head == nullptr && tail == nullptr) //아무 노드가 없다면
{
head = newNode;
tail = newNode;
}
else
{
newNode->next = head; //삽입된 노드의 다음노드는 기존의 head 노드
head = newNode; //맨앞의 노드는 삽입된 노드
}
size++; //노드 하나 들어갔으니 size 추가
}
void PushBack(T data) //뒤로 삽입하는 방식
{
Node* newNode = new Node;
newNode->data = data;
newNode->next = nullptr;
if (head == nullptr && tail == nullptr)
{
head = newNode;
tail = newNode;
}
else
{
tail->next = newNode; //tail 노드의 다음노드는 삽입노드
tail = newNode; //삽입노드가 새로운 tail 노드
}
size++;
}
void PopFront()
{
cout << "Remaining Node: " << size << '\n';
if (head == nullptr && tail == nullptr) //전부 삭제했다면
{
cout << "List is empty" << '\n';
return;
}
Node* deleteNode = nullptr;
if (size == 0)
{
deleteNode = head;
head = nullptr; //head 와 tail null로 초기화
tail == nullptr;
delete deleteNode; //남은 마지막 노드 삭제
}
else
{
deleteNode = head;
head = deleteNode->next;
delete deleteNode;
}
size--;
}
void Print() //리스트안의 노드들의 데이터값을 전부 보여주는 함수
{
Node* currentNode = nullptr;
currentNode = head;
while (currentNode != NULL) //currentNode 가 Null 이면 다 출력했기에 while문 나오기
{
if (currentNode == tail)
{
cout << currentNode->data;
}
else
{
cout << currentNode->data << " -> ";
}
currentNode = currentNode->next;
}
cout << '\n';
}
int Size()
{
return size;
}
~SingleLinkedList() //소멸자
{
while (size != 0) //남는 리스트 없을때까지
{
PopFront();
}
cout << "Release List" << '\n';
}
};
int main()
{
SingleLinkedList<int> singleLinkedList;
singleLinkedList.PushFront(100);
singleLinkedList.PushFront(99);
singleLinkedList.PushBack(98);
cout << "Single Linked List의 크기 : " << singleLinkedList.Size() << endl;
singleLinkedList.Print();
return 0;
}그림설명
Push
막 생성됬을 당시에는 head 와 tail은 현재 nullptr이다.
그러면 이제 10이라는 값을 pushfront해보자
데이터필드의 값이 10이들어가게되고 현재 맨앞은 새로만들어진 A노드이기에
head와 tail은 A노드를 가리킨다. 그다음으로 20이라는 값을 삽입시켜보자
새로운 B노드가 생기게되고 새로생긴 B노드의 링크 필드는 다음노드인 A노드를 가르키게되고 head=맨앞의 노드인 B노드를 가르켜주고 tail은 기존의 A노드가 맨마지막 노드이기에 A노드로 유지가된다 .
그다음 PushBack도 해보자.
30이라는 값을 넣었을때 C노드의 앞인 A노드의 다음노드를 C노드를 가르키게 해주고 맨마지막은 C노드이기에 tail노드는 C노드를 가르켜준다.
pop
단순연결리스트는 pop은 앞에서밖에 불가능하다 그도그럴것이 앞에서 다음노드를 가르키는 방식이다 보니 뒤에있는노드에서 앞에노드로 가는것이 어렵기 때문이다.(어떻게 구현하는방법은 있을거긴하니 한번 찾아보도록하겠다)
B노드를 없애기 위해 head 노드를 A노드로 가르키게 만들어준다.
이후 B노드의 링크필드를 nullptr로 만들고 delete 를 해준다.
마지막 C노드까지 삭제해주고 나면 다시 head 와 tail을 nullptr을 해준다.
이상으로 ..
이번에는 단방향연결리스트를 만들어보았을때 느낀점으로는 단방향연결리스트는 push에서는 구현이 간단하지만 pop을할때 동적할당한 노드를 삭제해야하다보니 조심할점이 많았던것같기도하고 , 단방향은 앞에서 다음노드 가기는 쉽지만 뒤에서 앞으로가는점이 힘든것으로 보인다. 이는 후에 이중연결리스트로 가능하기에 이중연결리스트때 다루어보도록하겠다.
