[자료구조] 단순 연결 리스트(Simple linked list) 와 이중 연결 리스트(Doubly linked list)

연결리스트(linked list)란?

• 연결리스트(Linked List)는 리스트의 항목들을 노드(Node)로 분산하여 저장하는 리스트이다.
• 노드(Node)의 구성으로는 데이터필드(데이터 저장) 와 링크필드(다른 노드의 주소값 저장)가 존재
• 장점 : 삽입과 삭제가 용이하며 연속된 메모리 공간이 필요 없기 때문에 크기 제한이 없다. 
• 단점 : 구현이 어렵고 까다롭고 오류가 방생하기 쉽다.
• 단순(단일) 연결 리스트, 이중 연결 리스트, 원형 연결 리스트 등이 있다.

---

단순 연결리스트(Simple linked list)에 대해 설명하시고 예제소스를 구현해보아라

• 하나의 링크 필드를 이용하여 하나의 방향으로 연결되어 있으며, 마지막 노드의 링크 값이 NULL인 연결리스트.
• 단점 : 한 노드에서 이전 노드의 역방향으로 노드를 탐색할 수 없다. 시간복잡도가 O(n)으로 속도가느리다.(맨처음 노드부터 탐색해야함)
• 예제
• addfront(element value) : 첫 노드에 추가
• addrear(delement value) : 마지막 노드에 추가
• void delfornt() : 첫 노드 제거
• void del(element value) : 특정 노드 제거
• void print_list(Node* Current) : 모든 리스트 출력

  #include <stdio.h>
  #include <stdlib.h>
  #include <malloc.h>
  
  typedef int element; 
  typedef struct Node
  {
  	element data;
  	struct Node* next;
  }Node;
  
  Node* pStart = NULL;		//리스트 처음
  Node* pEnd = NULL;			//리스트 마지막
  
  // 첫 노드에 추가
  void addfront(element value)
  {
  	Node* Current = (Node*)malloc(sizeof(Node));
  
  	Current->data = value;
  
  	if (pStart == NULL)
  	{
  		Current->next = NULL;
  		pStart = pEnd = Current;
  	}
  	else
  	{
  		Current->next = pStart;
  		pStart = Current;
  	}
  }
  
  // 마지막노드에 추가
  void addrear(element value)
  {
  	Node* Current = (Node*)malloc(sizeof(Node));
  
  	Current->data = value;
  	Current->next = NULL;
  
  	if (pStart == NULL)
  	{
  		pStart = pEnd = Current;
  	}
  	else
  	{
  		pEnd->next = Current;
  		pEnd = Current;
  	}
  }
  
  // 앞부분의 노드 제거
  void delfornt()
  {
  	if (pStart == NULL) return;
  
  	Node* Current = pStart;
  	pStart = pStart->next;
  	free(Current);
  
  }
  
  // 특정 노드 제거
  void del(element value)
  {
  	if (pStart == NULL) return;
  
  	if (pStart->data == value)
  	{
  		Node* Current = pStart;
  		pStart = pStart->next;
  		free(Current);
  		return;
  	}
  
  	Node* head = pStart;
  	Node* temp = head->next;
  
  	while (temp!=NULL)
  	{
  		if (temp->data == value)
  		{
  			head->next = temp->next;
  			free(temp);
  			break;
  		}
  		head = temp;
  		temp = head->next;
  	}
  }
  
  // 모든 리스트 출력
  void print_list(Node* Current)
  {
  	Current = pStart;
  	while(Current != NULL)
  	{
  		printf("%d->", Current->data);
  		Current = Current->next;
  	}
  	printf("NULL \n");
  }
  
  int main()
  {
  	for (int i = 0; i < 5; i++) {
  		addrear(i);
  		print_list(pStart);
  	}
  
  	for (int i = 0; i < 5; i++) {
  		delfornt();
  		print_list(pStart);
  	}
  
  	for (int i = 0; i < 5; i++) {
  		addfront(i);
  		print_list(pStart);
  	}
  
  	del(3);
  	print_list(pStart);
  
  	return 0;
  }
  /* 결과
  0->NULL
  0->1->NULL
  0->1->2->NULL
  0->1->2->3->NULL
  0->1->2->3->4->NULL
  1->2->3->4->NULL
  2->3->4->NULL
  3->4->NULL
  4->NULL
  NULL
  0->NULL
  1->0->NULL
  2->1->0->NULL
  3->2->1->0->NULL
  4->3->2->1->0->NULL
  4->2->1->0->NULL
  */

---

이중 연결리스트(Doubly linked list)에 대해 설명하시고 예제소스를 구현해보아라

• 두개의 링크 필드를 이용하여 양방향(이전 노드(previous),다음 노드(next))으로 연결 되어있다.
• 장점 : 앞,뒤로의 탐색이 가능하다. 
• 단점 : 이전 노드를 지정하기 위한 변수를 하나 더 사용해야 하기 때문에 단일 연결 리스트에 비해 메모리를 더 많이 사용한다. 또 구현이 복잡해진다. 

 

출처 및 참고 사이트 : https://salix97.tistory.com/283