Singly Linked List

개요

노드의 sequence를 담은 자료구조.

 

Array의 단점인 유연하지 못한 크기 조절을 해소한다.

 

 

SLL의 성질

각 노드는 다음 노드를 연결하여 단방향 순차 접근이 가능하다.

 

 

Node

각 노드는 값 (element)과 다음 노드의 주소를 가진다.

 

아래는 int형 element (data)와 다음 노드의 주소 (next)를 가지는 노드의 예시이다.

 

struct Node {
    int data;
    Node* next;
}

 

 

Singly Linked List 

SLL은 ADT로서 데이터 (노드), Operation (함수)를 가진다.

 

아래는 노드의 시작 주소 (head)와 간단한 함수들을 가지는 SLL의 예시이다.

 

struct SLL {
    Node* head;

    int at(int);
    bool empty();
    void addFront(int e);
    void removeFront();
}

 

 

Head에서 삽입

head에서 삽입은 다음과 같은 순서로 const time에 할 수 있다.

 

새 노드 N 할당 > N의 element 지정 > N의 next를 현재 head로 지정 > head가 N을 가리키게 함

 

아래는 구현 예시이다.

 

void addFront(int e) {
    Node* newNode = new Node();
    newNode->data = e;
    newNode->next = head;
    head = newNode;
}

 

 

Head에서 삭제

head에서 삭제는 다음과 같은 순서로 const time에 할 수 있다.

 

head가 기존 head에 연결된 노드를 가리키게 함 > 기존 head를 삭제

 

아래는 구현 예시이다.

 

void removeFront() {
    Node* oldHead = head;
    head = oldHead->next;
    delete oldHead;
}

 

 

Tail에서 삽입

tail의 주소를 기억한다면, tail에서 삽입 역시 다음과 같은 순서로 const time에 할 수 있다.

 

새 노드 N 할당 > N의 element 지정 > N의 next를 nullptr로 지정 > tail의 next를 N으로 지정 > tail이 N을 가리키게 함

 

아래는 구현 예시이다.

 

void addBack(int e) {
    Node* newNode = new Node();
    newNode->data = e;
    newNode->next = nullptr;
    tail->next = newNode;
    tail = newNode;
}

 

 

Tail 삭제

tail 삭제는 const time에 할 수 없다.

 

그 이유는 tail을 삭제하기 전 tail이 그 이전 노드를 가리켜야 하는데, 이 노드에 접근하려면 $O(n)$의 시간이 걸린다.

 

구현은 아래 구현 예시에서 확인할 수 있다.

 

 

Implementation

아래는 이론에서 배운 내용을 구현한 코드이다.

 

#include <bits/stdc++.h>
using namespace std;

/*

# addFront(e)	O(1)
# addBack(e)	O(1)
# remFront()	O(1)
# remBack(e)	O(n)
# at(i)		O(n)
# front()	O(1)
# back()	O(1)

*/

struct Node {
	int data;
	Node* next;

	Node(int e) {
		data = e;
		next = nullptr;
	}
};

struct SLL {
	Node* head;
	Node* tail;
	SLL() {
		head = nullptr;
		tail = nullptr;
	}
	~SLL() {

	}
	bool empty() {
		return (!head);
	}
	int front() {
		if (empty()) return -1;
		else return head->data;
	}
	int back() {
		if (empty()) return -1;
		else return tail->data;
	}
	int at(int i) {
		if (empty() || i < 0) return -1;
		Node* cur = head;
		while (i--) {
			if (!cur->next) return -1;
			cur = cur->next;
		}
		return cur->data;
	}
	void addFront(int e) {
		Node* newNode = new Node(e);
		newNode->next = head;
		head = newNode;
		if (!tail) tail = newNode;
	}
	int remFront() {
		if (empty()) return -1;
		Node* oldHead = head;
		int ret = oldHead->data;
		head = oldHead->next;
		delete oldHead;
		if (!head) tail = nullptr;
		return ret;
	}
	void addBack(int e) {
		Node* newNode = new Node(e);
		if (tail) tail->next = newNode;
		tail = newNode;
		if (!head) head = newNode;
	}
	int remBack() {
		if (empty()) return -1;
		int ret = tail->data;
		Node* newTail = head;
		while (newTail->next && newTail->next != tail) {
			newTail = newTail->next;
		}
		if (newTail == tail) {
			delete tail;
			tail = nullptr;
			head = nullptr;
		}
		else {
			delete tail;
			tail = newTail;
			tail->next = nullptr;
		}
		return ret;
	}
};

int main() {
	SLL A;
	int TEST; cin >> TEST; while (TEST--) {
		string oper; int p, q; cin >> oper;
		if (oper == "addFront") {
			cin >> p; A.addFront(p);
		}
		if (oper == "addBack") {
			cin >> p; A.addBack(p);
		}
		else if (oper == "removeFront") {
			cout << A.remFront() << "\n";
		}
		else if (oper == "removeBack") {
			cout << A.remBack() << "\n";
		}
		else if (oper == "front") {
			cout << A.front() << "\n";
		}
		else if (oper == "back") {
			cout << A.back() << "\n";
		}
		else if (oper == "empty") {
			cout << (A.empty() ? 1 : 0) << "\n";
		}
		else if (oper == "at") {
			cin >> p; cout << A.at(p) << "\n";
		}
	}
}