[자료구조] 3. 연결리스트

선형 리스트

리스트: 데이터를 순서대로 나열한 자료구조

가장 단순한 구조를 가진 리스트 = 선형리스트, 연결리스트

각 노드가 데이터와 함께 다음 노드를 가리키는 포인터를 가지고 있음

배열의 문제점

1. 쌓이는 데이터의 크기를 미리 알아야 함
2. 데이터의 삽입, 삭제에 따라 데이터를 모두 옮겨야하므로 효율이 좋지 않음

포인터로 연결리스트 만들기

연결리스트가 비어있는지 확인하는 법: head == NULL(head가 비었으면 리스트가 비어있음)

class Node {
public:
	int data;
	node* next;
	Node(int x, node* next = NULL) : data(x) , next(next){}
};

class List {
private:
	Node* head;
	Node* crnt;

노드 1개인 연결리스트 판단하는 법: head→next == NULL

노드가 2개인지 판단하는 법: head→next→next == NULL

머리노드인지 판단하는 법: p == head

꼬리노드인지 판단하는 법: p→next == NULL

 

직접 구현하는 방법은 책 참고

커서로 연결리스트 만들기

각 노드를 배열 안의 요소에 저장하고 그 요소를 잘 이용해 연결리스트를 구현하는 방법

앞에서 본 방법은 메모리 영역을 만들고 해제하는 과정이 필요했음

데이터의 개수가 크게 바뀌지 않고 데이터 개수의 최댓값을 미리 알 수 있다고 가정하면 배열을 사용해 효율적으로 연결리스트를 운용할 수 있음

배열의 커서는 포인터가 아닌 인덱스

class node{
public:
	int data;
	int next;
	int Dnext;
}

class List{
	node *n;  //리스트(배열)
	int head;
	int max;
	int deleted;
	int crnt;
}

배열의 비어있는 요소 처리하기

삭제를 여러번 하면 배열의 빈 레코드가 너무 많아져 효율이 떨어짐

프리리스트

삭제한 레코드를 관리하기 위해 사용하는 자료구조

Dnext: 프리리스트의 다음 노드를 가리키는 커서

deleted: 프리리스트의 머리 노드를 가리키는 커서

max: 배열의 가장 꼬리 쪽에 들어 있는 노드의 레코드 번호를 의미.

1. 레코드 5,1,3을 삭제하면 프리리스트는 3 → 1 → 5. deleted의 값은 3, 3번 노드의 Dnext값은 1, 1번의 Dnext는 5, 5번은 -1이 된다.
2. 새로운 값을 넣을 때 프리리스트의 머리노드값인 3을 사용해 3번 인덱스에 값을 넣고 프리리스트에서 3을 삭제해서 1→5상태로 만든다.
3. 레크드 7에 있는 값을 삭제하면 deleted에 7을 넣고 프리리스트를 7→1→5로 만들어준다.
4. 삭제한 레코드가 없어 프리 리스트가 비었다면 max값을 1증가시켜 배열꼬리의 아직 사용하지 않은 레코드를 사용한다.

원형 이중 연결 리스트

원형 리스트

꼬리노드가 머리노드를 가리킴

선형리스트에서 사용한 것과 같은 자료형을 사용할 수 있음

빈 원형 노드인지 확인: head == NULL

노드가 1개인 원형리스트 판단: head→next == head

머리노드인지 판단: p == head

꼬리노드인지 판단: p->next == head

이중 연결 리스트

선형리스트의 단점: 다음 노드는 찾기 쉽지만 앞쪽 노드는 찾을 수 없음.

이를 개선한 자료구조가 이중 연결 리스트

각 노드에는 다음 노드에 대한 포인터와 이전 노드에 대한 포인터가 주어짐

class node{
public:
	int data;
	node *prev;
	node *next;
}

머리노드인지 판단: p == head or p->prev == NULL

꼬리노드인지 판단: p->next == NULL

원형 이중 연결리스트

앞의 두 개념을 합한 연결 리스트

머리노드의 prev는 꼬리노드를 가리키고 꼬리노드의 next는 머리노드를 가리킴

원형 이중 연결리스트를 초기화 할 땐 비어있는 상태의 더미 노드 1개를 만들어서 리스트 초기화

더미노드는 노드의 삽입, 삭제를 수행하기 위해 리스트의 머리에 위치함.

리스트가 비어있는지 검사할 땐 head == head→next == head→prev이면 더미노드 하나만 있는 경우이므로 비어있음

검색은 ptr이 head가 아닐 동안 계속 next로 넘어가며 검색을 수행함. head가 더미노드이므로 검색을 시작하는 노드는 head가 아닌 head→next부터.

바로 다음에 노드를 삽입하는 경우(노드 B, D사이에 C를 삽입한다고 가정)

1. 새로 삽입할 노드를 만들고 만든 노드의 prev는 B, next는 D로 설정
2. 노드 B의 next를 C로 바꾸고 D의 prev도 C로 바꿔줌

이때 이미 리스트 머리에 더미노드가 있으므로 ‘비어있는 리스트에 삽입하는 경우’와 ‘리스트 머리에 삽입하는 경우’는 따로 처리하지 않아도 됨

노드를 삭제할 땐 삭제할 노드를 p라고 하면 p→prev→next = p→next, p→next→prev = p→prev 로 바꿔주고 p의 메모리를 해제하면 됨

노드를 삭제할 때 더미노드를 삭제하지 않도록 주의해야함