Chap 02. 연결리스트

리스트에는 순차리스트와 연결리스트가 있다.

'순차리스트'는 '배열'을 기반으로 구현된 리스트.
'연결리스트'는 메모리의 '동적 할당'을 기반으로 구현된 리스트.

- 배열
장점 : 접근이 빠르다
단점 : 메모리 사용 비효율적,데이터 삭제시 배열 처리 번거로움

- 연결리스트
장점 : 메모리 사용 효율적
단점 : 접근이 느리다

 

---

'연결리스트'를 공부하기에 앞서
다음 코드를 보자

typedef struct _node
{
	int data;  //데이터를 저장할 장소
	struct _node* next;  //다른 변수를 가리키기 위한 장소
}Node;

 

 

Node 자체를 바구니라 지칭한다면, 
바구니는 '구조체 멤버 next'를 통해 연결이 되어있다.

 

---

 '연결리스트'에 데이터를 [1,2,3,4,5] 순차적으로 추가할때, 

연결리스트는 데이터 추가를 head에 추가할지 ex) head->5->4->3->2->1->NULL 
                                     tail에 추가할지 ex) head->1->2->3->4->5->NULL 
정해야한다. 

-head 
장점 : 포인터 변수 tail이 필요없다. 
단점 : 저장된 순서를 유지하지 않는다. (순서는 1,2,3,4,5이지만 저장내용은 5,4,3,2,1) 

-tail 
장점 : 저장된 순서가 유지된다. 
단점 : 포인터 변수 tail이 필요하다. 

● 포인터 변수 tail을 추가하기 위해 부가적인 코드가 번거롭게 느껴질수 있다. 
● 리스트는 저장된 순서를 유지하는 자료구조가 아니다. 
● 대체적으로 head에 Data를 추가한다.

---

● 연결리스트 데이터 삽입

while(1){ 
	newNode = (Node*)malloc(sizeof(Node));  //Node 생성
	newNode -> data = readData; 		//data 저장
	newNode -> next = NULL; 		//연결한 노드 X

	if(head == NULL) 			//연결리스트에 노드가 없다면
		head = newNode; 		//첫번째(head)에 newNode를 가리키겠다.
	else 
		tail->next = newNode; 		//마지막 노드가 newNode를 가리키게하겠다.

	tail = newNode; 			//newNode가 마지막 노드가 된다.
} 

 

>> 계속 head가 비었는지 확인을 해주어야함. 
>> tail에 데이터를 추가해줌.

===>> 번거로움

---

● 연결리스트 데이터 삽입 - 더미노드

void FInsert(List* plist,LData data) 
{
	Node * newNode = (Node*)malloc(sizeof(Node)); 	//newNode 생성
	newNode->data = data; 

	newNode->next = plist->head->next; 		
	plist->head->next = newNode; 

	(plist->numOfData)++; 
}  

 

>> 연결리스트 head는 더미노드(쓰레기노드) 저장.
>> 노드앞에서부터(head부터) 데이터 추가
>> 즉, 연결리스트 head가 비었는지 확인 없이 head->next에 newNode 저장

---

● 연결리스트 데이터 출력과정

---

● 연결리스트 데이터 삭제과정

---

● 원형 연결리스트
 
- 단순 연결리스트에서 마지막 노드가 첫번째 노드를 가리킨 것

특징 : 
- 보통 head 포인터 변수를 두지만 원형 연결리스트는 tail을 포인터 변수를 둔다.

장점 : 
- 포인터 변수 tail 하나로 머리 또는 꼬리에 노드를 추가할 수 있다.

즉, 꼬리를 가리키는 포인터 변수 = tail
    머리를 가리키는 포인터 변수 = tail->next

---

● 양방향 연결리스트

typedef struct _node 
{ 
	Data data; 
    struct _node * next; 
    struct _node * prev; 
    
}Node; 

 

prev 포인터 변수가 있기 때문에 before 포인터 변수는 필요없다.

 

출처 : 윤성우의 열혈 자료구조