포인터와 연결 리스트

Concept | Linked list

* 노드(Node): <항목, 주소>의 쌍

- 노드는 데이터 필드와 링크 필드로 구성된다.

    - 데이터 필드: 리스트의 원소, 즉 데이터 값을 저장한다.

    - 링크 필드: 다른 노드의 주소값을 저장하는 장소로, 포인터의 역할을 한다고 보면 된다.

cf) 배열은 데이터 필드로만 구성된다.

- 메모리 안에서의 노드의 물리적 순서가 리스트의 논리적 순서와 일치할 필요는 없다.

cf) 배열은 서로 연속되는 공간에 데이터가 저장되기 때문에 일치한다.

 

🐢 linked list 장점

    - 삽입과 삭제가 용이하다. (배열의 단점을 해결한 부분)

    - 연속된 메모리 공간이 필요 없다.

    - 크기의 제한이 없다. (Dynamic Memory Allocation)

🐢 linked list 단점

    - 구현이 비교적 어렵다.

    - 오류가 발생하기 쉽다.

    - direct access가 어렵다. (performance 문제)

    --> 배열의 장점이기도 하다. 배열은 인덱스를 활요하여 direct access가 가능하다.

 

🐢 linked list 구조

    - 헤드 포인터(head pointer): 리스트의 첫 번째 노드를 가리키는 변수

    --> linked list는 클래스를 만들면 head pointer만 있으면 된다.

 

🐢 linked list의 종류

    - simply linked list

    - circular linked list

    - doubly linked list

 

🐢 linked list로 stack 구현하기

- 삽입 연산

    ! 앞 쪽에 Node 삽입

    1. 노드 D의 링크 필드가 노드 C를 가리키도록 한다.

p->link=top;
// 여기서 top은 앞서 말했던 head pointer

    2. top이 노드 D를 가리키도록 한다.

top=p;

 

 

 

     ! linked list에서 순서 중요하다.

    1과 2의 순서를 바꾸면 안된다. (순서를 바꾸게 되면 C를 가리키는 주소를 찾을 수 없다. top의 값이 먼저 바뀌면 그냥 외딴 섬이 되어버린다.)

- 삭제 연산

    1. 포인터 변수 p가 노드 C를 가리키도록 한다.

    2. head pointer top이 B를 가리키도록 한다.

    3. 변수 p의 값을 반환한다.

p=top;					// 1.
top=p->next;			// 2.
// top=top->next; 도 가능하지만
// 스택에서 pop을 해줘야 하므로 top의 내용이 사라지기 때문에 전 주소를 다시 access 할 수 없다.

return p;				// 3.

cf) display 같은 리스트 전체 출력 함수 구현 (전체 노드를 방문하는 순회 traverse) 시,

// 전형적인 linked list traverse
for(Node *p=top;p!=NULL;p=p->link){}

// p!=NULL 대신 p만 적어도 좋다.
for(Node *p=top;p;p=p->link){}

! stack에서는 top 1개의 포인터만 가진다.

 

🐢 linked list로 queue 구현하기

! 삽입은 뒤에서, 삭제는 앞에서

- 삽입 연산

    - 공백상태에서의 삽입

    - 공백상태가 아닐 때의 삽입

rear->link=p;
rear=p;

 

- 삭제 연산

    - 노드가 2개 이상인 경우의 삭제

p=front;			// 임시 변수에 front 넣어두기
front=p->link;

    - 노드가 1개인 경우의 삭제

p=front;
front=p->link;

rear=NULL;

// queue에서의 삭제 연산
Node *dequeue(){
	if(isEmpty()) return NULL;		// 노드가 빈 경우
    
    Node *p=front;					// 노드가 2개 이상인 경우
    front=front->link;
    
    if(front==NULL) rear=NULL;		// 노드가 1개인 경우
    
    return p;
}

! queue에서는 front, rear 2개의 포인터를 가진다.