[자료구조] List

자료구조 ／ 알고리즘/자료구조

by 부레두 2024. 2. 29. 00:07

1. List

인덱스를 이용한 순서와 위치를 가져 추출과 추가가 용이

2. 종류

Linked List

배열과 달리 새로운 데이터를 중간 추가, 삭제가 쉬움
특정 데이터의 추출이 어려움
구현의 난이도가 높음

예시

단순 연결 리스트 : 선형의 단순한 형태의 리스트

링크드 리스트 예시 코드

// LinkedList.cpp #include "LinkedList.h" #include <iostream> using namespace std; 
// 노드 생성 
Node* Create(DataType data) 
{ 
	Node* node = new Node(); 
    node->Data = data; 
    node->NextNode = NULL; 
    return node; 
} // 노드 삭제 

void Destroy(Node** node) 
{ 
	delete node; node = NULL; 
} 

// 노드 추가 
void Push(Node** head, Node* node) 
{ 
	if(*head != NULL) 
    { 
    	Node* tail = (*head); 
        
        while (tail->NextNode != NULL) 
        tail = tail->NextNode; 
        tail->NextNode = node; 
     } 
     else 
     { 
     	// 생성해서 리턴해주기 위해 이차포인터 사용 
        *head = new Node(); 
     } 
 } 
 
 // 노드 중간 삽입
 void Insert(Node* current, Node* node)
 { 
 	node->NextNode = current->NextNode; 
    current->NextNode = node; 
 } 
 
 // 헤드 삽입 
 void InsertHead(Node** current, Node* head) 
 { 
 	if(*current == NULL) 
    { 
    	*current = head; 
    } 
    else 
    { 
    	head->NextNode = *current; 
        *current = head; 
     } 
  } 
  
  // 삭제 
  void Remove(Node** head, Node* remove) 
  { 
  		if(*head == remove) 
        { 
        	*head = remove->NextNode; 
        } 
        else 
        { 
            Node* current = *head; 
            
            while (current != NULL && current->NextNode != remove) 
            current = current->NextNode; 
            if (current != NULL) current->NextNode = remove->NextNode; 
        } 
   } 
   
   // 노드 임의 접근 
   Node* GetNode(Node* head, int location) 
   {
   		Node* current = head; 
   		while (current != NULL && (--location >= 0)) 
        { 
        	current = current->NextNode;
        } 
        
        return current; 
  } 
  
  // 노드 갯수 확인 
  int GetNodeCount(Node* head) 
  { 
  		int count = 0; 
        Node* current = head; 
        
        while (current != NULL)
        { 
        	current = current->NextNode; count++;
         } 
         
         return count; 
  }

이중 연결 리스트

다음 노드 뿐 아니라 이전 노드의 참조도 포함한 리스트

이중 연결 리스트 예시 코드

// 노드 생성
Node* DL_Create(DataType data) 
{ 
	Node* node = new Node(); 
    node->PrevNode = NULL; 
    node->Data = data;
    node->NextNode = NULL;
    
    return node; 
} 

// 노드 제거 
void DL_Destroy(Node** node) 
{ 
	delete node; node = NULL; 
} 

// 노드 추가 
void DL_Push(Node** head, Node* node) 
{ 
	if(*head != NULL) 
    { 
    	Node* tail = (*head);
        
        while (tail->NextNode != NULL)
        tail = tail->NextNode; 
        tail->NextNode = node; 
        node->PrevNode = tail; 
     } 
     else 
     { 
        // 생성해서 리턴해주기 위해 이차포인터 사용 
        *head = new Node(); 
     } 
} 

// 노드 삽입
void DL_Insert(Node* current, Node* node) 
{ 
	node->NextNode = current->NextNode; 
    node->PrevNode = current; 
    
    if (current->NextNode != NULL) 
    	current->NextNode->PrevNode = node; 
        
    current->NextNode = node; 
} 

// 노드 맨앞에 추가 
void DL_InsertHead(Node** current, Node* head) 
{ 
	if(*current == NULL) 
    { 
    	*current = head; 
    } 
    else 
    { 
    	head->NextNode = *current; 
        *current = head; 
    } 
} 

// 노드 리스트에서 제거 
void DL_Remove(Node** head, Node* remove) 
{ 
	if(*head == remove) 
    { 
    	*head = remove->NextNode; 
        
        if (*head != NULL) 
        (*head)->PrevNode = NULL; 
        
        remove->NextNode = NULL; 
        remove->PrevNode = NULL; 
    } 
    else 
    { 
    	Node* current = remove; 
        remove->PrevNode->NextNode = current->NextNode; 
        
        if (remove->NextNode != NULL) 
        	remove->NextNode->PrevNode = current->PrevNode; 
            
        remove->PrevNode = NULL; remove->NextNode = NULL; 
     } 
 } 
 
 Node* DL_GetNode(Node* head, int location) 
 { 
 	Node* current = head; 
    
    while (current != NULL && (--location >= 0)) 
    { 
    	current = current->NextNode; 
    } 
    
    return current; 
} 

int DL_GetNodeCount(Node* head) 
{ 
	int count = 0;
    
    Node* current = head; 
    while (current != NULL)
    { 
    	current = current->NextNode; count++; 
    } 
    
    return count; 
}