Linked List

728x90

Definition of Linked List

Consists of Nodes
Node: unit of storage (item)
Nodes are linked with pointers(link) - 포인터가 옆에 붙어있다 (what does that mean?)

메모리 아무 곳에나 흩어져있음
논리적으로는 1차원
pointer to next node : 단순히 주소가 저장되어 있는 것

Q. 화살표는 코드에서 무슨 뜻일까?

A. 다음 노드의 주소가 값으로 적혀있다

화살표를 따라가면 다음 노드가 어디에 있는지 알 수 있다

프로그램의 head는 변수로 가지고 있어야한다 - head는 노드가 아니다

Code of node

class Node {
	int a;
	Node *n;
};

Q. node 옆에 *이 없다면 어떻게 될까

A. 노드가 아예 안에 들어가 있는 형태가 되기 때문에 컴파일이 되지 않음

→ 별이 없으면 사이즈를 정할 수 없음 노드 안에 노드 이런 방식이 무한히 이어지기 때문이다

Code of List

class List {
    List();
    ~List();
    int Search(…);
    int Insert(…);
    int Delete(…);

    Node *head;
};

…

    List A;
    A.head = NULL; if (A.Search(8)) {…}

시작할 때는 head 하나만 있으면 됨

Q. List A는 몇 바이트?

A. 함수는 들어가지 않고 들어가는 것은 Node *head 뿐이기 때문에 포인터가 4byte인지 8byte인지에 따라 4, 8바이트가 됨

*new를 해야 변수가 새로 생기는 것임

Construction, Destruction (생성자, 제거자)

변수가 생성될 때, 제거 될 때 사용됨

//생성자
List::List()
{
    head = NULL;
    // 처음 만들 때 head가 가르키는 것이 없다는 것
}
 //제거자
List::~List()
{
	//제거가 되면, 뒤에 있는 얘들도 전부 제거가 되어야함
    Node *p, *q;
	p = head; //p가 head가 가리키는 곳을 같이 가리키도록 함 (주소를 복사한것) -> 첫번째 노드를 가르킨다
	while (p != NULL){
		q = p->n;// p가 가리키는 있는 곳이 가리키고 있는 노드
		delete p; // free => p가 가리키고 있는 그 곳을 버리는 것
        // 내용을 지우는 것이 아닌, 다시 사용할 수 있다고 표시해주는 것
		p = q
	}
}

Q. 언제 생기는지?

A. 변수가 생기는 방법은 3가지가 있다

프로그램이 시작할 때 global 변수
함수 안에 있는 변수 > 함수가 호출 될 때 스택에 생김 return하면 없어짐
new를 하면 생성됨 > 어떤 방식으로?

*new 실행 : malloc을 불러서 사용하지 않은 heap에 사용한다는 표시를 함 >> delete나 free가 오면 쓰지 않는다고 표시함

*free or delete를 실행하지 않으면 결국 메모리가 부족해짐 >> memory leak

Q. 없애면 어떤 일이 생기는가?

A. delete or free 와 같은 일을 함

Search

int List :: Search(int x, node **p, Node **l){
	*p = NULL; *l = head; 
    //P가 NULL을 가리키고 있음
    //L이 head의 노드를 가리키고 있음 
	while(*l != NULL){
		if((*l) -> a > x) return 0; //L이 가리키는 노드 (시작은 head와 같음)의 값이 x보다 클때
		else if((*l) -> a == x) return 1; //찾은거임
		else {*p = *l; *l = (*l) -> n;} //P가 L이 가리키던 곳을, L은 그 다음을 가리킴
	}
	return 0;
}

Node *P, *L;
res = A.Search(8, &P, &L); // P와 L의 주소를 보냄 > 따라서 **

값이 sorting 이 되어있다는 가정

P, L : insert 와 delete를 위함

l : location

p : previous

Insert

int List :: Insert(int x){
	Node *P, *L, *N;
	if(Search(x, &P, &L) == 0){ //search가 실패했을 때만 시도
		N = new Node; N-> a = x; //x라는 값이 들어간 노드를 만듦
		if (P == NULL) head = N; //시작일 때
		else P -> n = N; 
		N -> n = l;
		return 1;
	}
	return 0;
}

Q. new가 생성되지 않을 때는 ?

A. 메모리가 없는 것

Delete

int Delete(int x, Node **d){
		Node *P, *L;
		if(Search(x, &P, &L) == 1){ //search가 성공했을 때 
        //P가 L의 다음 노드를 가리키도록 해야함
			if(P == NULL) head = L -> n; //시작일 때
			else P -> n = L -> n;
			return 1;
		}
		return 0;
}

Performance

Sorted

search : O(n)

Insert : S + O(1)

Delete : S + O(1)

Unsorted

search : O(n)

Insert : S + O(1)

Delete : S + O(1)

>> 그래도 따지자면 sorting 된 것이 미세하게 빠름

LRU (Least Recently Used, Paper on Desktop) : unsorted - 빈도가 차이가 클수록 효과가 좋음

최악:: Search: O(n), Insert: O(1), Delete: S + O(1)

기대:: 사용 빈도에 따라 크게 다름

Comparison with std: vector (vector을 사용하는 경우의 성능 비교)

Vector: Variable-Size Array (배열을 통째로 복사하고 그 곳에 넣어야함 > 2배씩 늘리기)

Sorted : Search: O(log n), Insert: S + O(n), Delete: S + O(n)

Unsorted : Search: O(n), Insert: S + O(1), Delete: S + O(1)

List

Dummy Node

-무한, +무한은 사용하지 않는 노드인 것이다
아예 안 쓰는 값으로 두 개를 넣어두면, 항상 앞과 뒤의 노드가 있음
메모리를 조금 더 쓴다는 단점이 존재함

Circular List

Doubly Linked List

앞 뒤로 갈 수 있음
라이브러리 Linked List는 dummy circular doubly linked list의 총 집합체임

* 배열과 스택의 근본적인 차이

배열 : 연속된 주소의 같은 타입

스택 : 나중에 들어온게 먼저 나간다

>> 배열로 스택을 만드는 것은 구현의 한 버전일 뿐임

Application

Equivalence Relation

Linked Stack

insert를 맨 앞에 하면 됨, delete를 맨 앞에 하면 됨
배열 구현보다는 느리지만, 사이즈의 제한이 없음

Linked Queue

insert는 끝에 하는것이 편함 (tail)
delete는 head에 하는 것이 편함

기술

unsorted unpacked

그 외에도 다항식 표현 등에 사용할 수 있음

2차원 배열인데 0이 되게 많은 것

Linked List로 표현할 수도 있다는 것

class Node {
    int a, r, c;
    Node *up, *down, *left, *right;
}

Memory Allocation

전체를 linked list로 가지고 있음
안쓰는 곳이 이어져 있으면 그것을 한 덩어리로 생각함
malloc 하는 코드를 보면 실제로 linked list로 구현되어있음

Skip List

중간으로 가는 link가 존재함
2배 빨라짐
binary search를 할 수 있음
insert를 어떻게 할까?

B+ Tree

내려가면서 달라지는 구조를 tree
제일 아래에 linked list를 달아놔서 옆으로 갈 수 있도록 함