[알고리즘/C++] - 링크드리스트,,(LInkedList)

안녕하세요 오늘은 링크드리스트(LinkedList)에 대해서 알아보도록 하겠습니다..

이름이 너무 정직해서 아재드립을 칠 수가 없다는 사실이 너무나도 안타깝습니다..

아쉬운대로 메이플 스토리 링크 스킬을 가져와봤습니다..

성에 차지 않네요,,

 

추상적 자료형인 리스트를 구현한 자료구조로, Linked List라는 말 그대로 어떤 데이터 덩어리(이하 노드Node)를 저장할 때 그 다음 순서의 자료가 있는 위치를 데이터에 포함시키는 방식으로 자료를 저장한다. 예를 들어 한 반에 있는 학생들의 자료를 저장한다면, 학생 하나하나의 신상명세 자료를 노드로 만들고, 1번 학생의 신상명세 자료에 2번 학생 신상명세가 어디있는지 표시를 해 놓는 방식이다. 쉽게 생각하면 자료를 비엔나 소시지마냥 줄줄이 엮어놓은 것이다.
- 나무위키

 

자 오늘도 나무위키와 함께하는 알고리즘.!

쉽게 소시지를 엮어놓은 모습, 앞 데이터는 다음 데이터의 위치를 알고 있습니다. 

연결 리스트는 말 그대로 양 옆 데이터들이 서로 얽혀있다고만 알아두면 좋습니다.

 

하지만 연결리스트는 연결하는 방법에 따라 세 가지의 종료로 나뉘게 됩니다.

단순 연결 리스트(Singly LInked List)

이중 연결 리스트(Doubly Linked List)

순환 연결 리스트(Circular Linked List)

 

이번 시간에는 연결 리스트라고 했을 때 가장 단순하면서도 쉽게 떠올리는 단순연결리스트에 대해서 알아보고, 다음 포스팅에서 추가로 이중 연결 리스트에 대한 개념과 코드를 살펴보겠습니다.

 

단순 연결 리스트(Singly LInked List)

단순 연결리스트는 각각의 데이터가 자신이 가지고 있는 값, 그리고 다음에 있는 데이터의 위치(주소)를 가리치키는 값. 이렇게 두가지의 값을 가집니다. 

이러한 구조로 인해 연결리스트에서 데이터를 참조하는 경우에는 데이터의 길이가 길면 길수록 처음 값부터 두 번째값으로, 두번째 값에서 세번째 값으 계속해서 이동하여 값을 찾아야하기 때문에 시간복잡도가 O(n)의 구조를 가진다는 특징이 있습니다.

 

이 자료구조는 첫번째(Head)의 값을 잃어버린다면, 다음으로 갈 방법 또한 사라져버리기 때문에 데이터 전체를 쓸 수 없게 되어버린다는 점. 이에 더해서 중간에서도 하나라도 주소를 잘못참조하는 등의 문제가 생겨도 나머지 뒤 데이터들을 유실해버리기 때문에 안정적이지 않은 자료구조라고 합니다.

---

저는 단일 연결 리스트를 통해 스택의 기능들을 구현하는 응용 작업을 진행해보았습니다.

이 작업을 진행할 때 유의할 점은, 여기서 계속해서 접근하는 헤드(최상단)는 스택에서의 가장 나중에 들어오는 꼬리 데이터와 같습니다. 

또한 데이터를 연결할 때에도 기존의 개념대로라면 단순 연결리스트이기 때문에 각각의 데이터가 다음 데이터의 주소를 참조하고 있어야하지만 스택의 경우에는 그와 반대로 각각의 데이터가 이전 데이터의 주소를  참조합니다.

따라서, 기존 연결리스트에서 방향이 반대로 된 느낌으로 보면 좋을 것 같습니다.

//단일 연결 리스트로 스택 만들기
#include <iostream>
#define MAX 10 

using namespace std;

struct Position
{
	int x, y;
};

struct Node
{
	Position xy; //값
	Node* pNext; //다음 데이터를 가리킬 주소
	Node() { //첫 선언시 null로 초기화
		pNext = NULL;
	}
};

struct Stack {
	Node* head = nullptr;	//탑(최상단)포인터

	~Stack() { //데이터가 빌 때까지 삭제
		while (!Empty()) {
			Pop();
		}
	}

	bool Empty() { //헤드가 없다면 비어있다고 간주
		return head == nullptr;
	}

	int Size() {
		int size = 0;
		Node* next = head;
		while (1) {
			if (next == nullptr)
				return size;
			else {
				next = next->pNext;
				size++;
			}
		}
		return size;
	}

	void Push(Position n) {
		Node* news = new Node; //새로운 값 생성
		news->xy = n;
		news->pNext = head;//새로운 값에 최상단 주소값 연결
		head = news; //최상단을 새로운 값으로
	}

	void Pop() { 
		if (Empty()) return;
		Node* temp = head; //최상단 데이터를 가리키는 포인터
		head = head->pNext; //최상단 데이터를 이전 데이터로 이동
		delete temp; //포인터를 통해 데이터 삭제

	}

	Position Top() { //헤드(최상단)의 데이터 반환
		if (head == nullptr)return { 0,0 };
		return head->xy;
	}
};

C++은 list 라이브러리를 통해 연결리스트를 제공하고 있습니다.

 

https://solved.ac/problems/tags/linked_list

solved.ac

그럼 오늘도 여기까지!

모두 즐거운 하루되세요 

안

녕

반응형