리스트의 종류 (링크드, 더블 링크드, 환형 링크드)

1. 링크드 리스트

리스트의 자료구조를 구현 방법 중 하나입니다.

일반적으로 시작 노드를 head 노드, 끝 노드를 tail 노드라고 정의합니다.

 

 

링크드 리스트의 ADT

링크드 리스트의 ADT를 정의하기 위해 공통 요소와 기능을 살펴보겠습니다.

• 요소(DATA): 개별 노드(Node), head 노드에 대한 포인터
• 기능(FUNCTION):
  • 노드를 추가하는 연산
  • 노드를 삽입하는 연산
  • 노드를 제거하는 연산
  • 노드를 반환하는 연산

 

링크드 리스트의 ADT 선언

링크드 리스트의 ADT를 보고 선언만 해보겠습니다.

typedef int nodeData;
typedef struct Node
{
		Node*    next;
		NodeData nodeData;
		
}*PNODE, NODE

class LinkedList
{
public:
	List();
	~List();

public:
	void   appendNode();
	void   insertNode();
	void   removeNode();
	PNODE  searchNode(nodeData data);   
	
private:
	PNODE head;
}

 

코드 분석

• 링크드 리스트의 요소에 들어가는 데이터를 위해 Node 구조체를 선언합니다
• 리스트의 요소는 PNODE 타입의 head입니다.
• 리스트의 기능은 노드의 추가, 삽입, 삭제, 탐색이 있습니다.

 

 

2. 더블 링크드 리스트

리스트의 자료구조를 구현 방법 중 하나입니다.

일반적으로 시작 노드를 head 노드, 끝 노드를 tail 노드라고 정의합니다.

 

 

더블 링크드 리스트와 링크드 리스트의 차이

더블 링크드 리스트의 경우 노드 사이에서 양 방향 이동이 가능합니다.
(이전 노드 -> 다음 노드 | 다음 노드 -> 이전 노드)

하지만 링크드 리스트의 경우에는 head → tail 방향의 단 방향 이동만 가능합니다.
(head 노드부터 끝 노드까지 단방향 이동만 가능)

 

 

더블 링크드 리스트의 ADT

더블 링크드 리스트의 ADT를 정의하기 위해 공통 요소와 기능을 살펴보겠습니다.

• 요소(DATA): 개별 노드(Node), head노드에 대한 포인터
• 기능(FUNCTION):
  • 노드를 추가하는 연산
  • 노드를 삽입하는 연산
  • 노드를 제거하는 연산
  • 노드를 반환하는 연산

 

 

typedef int nodeData;
typedef struct Node
{
		Node*    next;
		Node*    prev;
		NodeData nodeData;
		
}*PNODE, NODE

class DoubleLinkedList
{
public:
	List();
	~List();

public:
	void   appendNode();
	void   insertNode();
	void   removeNode();
	PNODE  searchNode(nodeData data);   
	
private:
	PNODE head;
    PNODE tail;
}

코드 분석

• 링크드 리스트의 요소에 들어가는 데이터를 위해 Node 구조체를 선언합니다
• 링크드 리스트와 달리 Node 구조체에 prev라는 포인터 변수가 하나 더 생겼습니다.
  이는 이전 노드의 주소값을 알아야 이동할 수 있기 때문입니다.
• 리스트의 요소는 PNODE 타입의 head, tail입니다.
• 리스트의 기능은 노드의 추가, 삽입, 삭제, 탐색이 있습니다.

 

3. 환형 링크드 리스트

 

링크드 리스트와 환형 링크드 리스트의 차이.

링크드 리스트의 경우에는 head와 tail노드가 연결되어 있지 않습니다.

하지만 환형 링크드 리스트의 경우에는 head와 tail 노드가 연결되어 있습니다.

head에서 tail로의 직접 이동이 가능해집니다.

 

환형 링크드 리스트의 ADT

환형 링크드 리스트의 ADT를 정의하기 위해 공통 요소와 기능을 살펴보겠습니다.

• 요소(DATA): 개별 노드(Node), head노드에 대한 포인터
• 기능(FUNCTION):
  • 노드를 추가하는 연산
  • 노드를 삽입하는 연산
  • 노드를 제거하는 연산
  • 노드를 반환하는 연산

typedef int nodeData;
typedef struct Node
{
		Node*    next;
		Node     prev;
		NodeData nodeData;
		
}*PNODE, NODE

class CircleLinkedList
{
public:
	List();
	~List();

public:
	void   appendNode();
	void   insertNode();
	void   removeNode();
	PNODE  searchNode(nodeData data);   
	
private:
	PNODE head;
    PNODE tail;
}

코드 분석

• 링크드 리스트의 요소에 들어가는 데이터를 위해 Node 구조체를 선언합니다
• 더블 링크드 리스트와 Node 구조체의 큰 차이점은 없습니다.
• 리스트의 요소는 PNODE 타입의 head, tail입니다.
• 리스트의 기능은 노드의 추가, 삽입, 삭제, 탐색이 있습니다.
• 더블 링크드 리스트와 큰 차이가 없어보이나, 환형 링크드 리스트는 head의 이전 노드가 tail, tail의 다음 노드가 head지만 더블 링크드 리스트는 tail의 다음 노드는 nullptr이고, head의 이전 노드도 nullptr입니다.