리스트

리스트란?

리스트(List)는 목록 형태로 이루어진 데이터 형식입니다. 리스트를 구성하는 개별 요소를 노드(Node)라고 부르며, 리스트의 첫 번째 노드를 헤드(Head), 마지막 노드를 테일(Tail)이라고 합니다.

 

 

ADT 정의

자료구조를 구현하기 전에 해당 자료구조의 ADT(Abstract Data Type)를 정의할 필요가 있습니다. ADT라는 용어가 처음에는 다소 모호하게 느껴질 수 있지만, 이는 추상화된 자료 구조를 의미합니다. 추상화는 객체의 공통적인 요소와 기능을 정의하는 것을 의미하며, 프로그래밍에서는 요소를 데이터(Data), 기능을 함수(Function)로 구현합니다. 

ADT는 자료구조를 객체라는 관점으로 바라보면, 자료구조의 공통적인 요소와 기능을 정의하는것으로 볼 수 있습니다.

 

 

리스트의 ADT

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

• 요소(DATA): 개별 노드(Node)
• 기능(FUNCTION):
  • 노드를 추가하는 연산
  • 노드를 삽입하는 연산
  • 노드를 제거하는 연산
  • 노드를 반환하는 연산

 

리스트의 ADT 선언

리스트의 ADT를 확인하고 이를 선언만 해보겠습니다.

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

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

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

 

코드 분석

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

위와 같이 선언된 리스트는 기본적인 요소와 기능을 갖추고 있으며, 각 리스트의 유형에 따라 요소와 기능의 선언이 약간씩 달라질 수 있습니다.