자료구조&알고리즘 (18) 썸네일형 리스트형 [이중 연결 리스트] 노드 구조체, 노드 생성, 노드 맨 앞 추가, 생성 된 순서의 역순 연결 이중 연결 리스트의 노드를 맨 앞에 삽입하는 함수에 대한 샘플 코드를 작성해보자. 이중 연결 리스트는 노드의 왼쪽과 오른쪽의 값이 서로 연결되어 있는 자료구조이다. 1. 구조체 정의 typedef struct doublyNode { int value; struct doublyNode* next; struct doublyNode* prev;} DNode; 이중 연결 리스트의 노드를 정의하는 구조체이다. 각 노드는 값 (value), 다음 노드에 대한 포인터(next),이전 노드에 대한 포인터(prev)를 가진다. 2. 전역 변수 DNode* head = NULL;DNode* tail = NULL;리스트의 시작과 끝을 가리키는 head , tail 포인터를 NULL 값으로 초기화해준다. .. [단일 연결 리스트] 문자열 노드 전체 제거 단일 연결 리스트에서 모든 문자열 노드를 제거하는 방법에 대해 알아보도록 하자. 기존에 int나 double 같은 데이터가 포함된 노드를 제거할 때는 단순히 노드 자체만 제거하면 끝났다. 하지만 문자열이 포함된 노드를 제거할 때는 상황이 다르다. 예를 들어, "apple"이나 "strawberry"와 같은 문자열은 malloc을 통해 동적 할당된 메모리이다. 따라서, 문자열 연결 리스트의 노드를 제거할 때는 다음과 같은 두 가지 작업을 모두 수행해야 한다. 문자열에 할당된 동적 메모리 해제노드 자체의 메모리 해제여기서 중요한 점은 노드를 제거하기 전에 반드시 문자열의 메모리를 먼저 해제해야 한다는 것이다. 만약 노드를 먼저 제거하면 문자열의 주소를 가리키던 포인터가 사라져서 문자열의 메모리를 해제할 .. [단일연결리스트] 노드 정렬 삽입(오름차순) 노드를 정렬하면서 삽입을 할 때 기본적인 고려사항은 크게 4가지가 있다. 1. head == NULL2. 가장 작은 값 삽입3. 일반적인 경우4. 가장 큰 값 삽입 4가지 케이스 별로 오름차순으로 노드 정렬 삽입을 구현한 예제 코드이다. #include #include typedef struct node { int value; struct node* next;} node;node* head = NULL;void insertNodeSort() { node* newNode = (node*)malloc(sizeof(node)); scanf("%d", &newNode->value); newNode->next = NULL; //head == NULL 일떄 if (head .. [단일 연결 리스트 ] 특정 값 노드 삭제 | 중간 값 삭제 단일 연결 리스트에서 중간 위치에 있는 노드를 삭제할 때는 삭제한 노드 양 옆에 있는 노드들을 연결해주면 된다.그러나 head가 딸려있는 맨 첫번째 노드를 지울 때는 head 도 이동해야하기 때문에 첫 노드를 삭제하는 케이스, 중간 노드를 삭제하는 케이스 투스텝으로 나누어 코드를 작성하면 된다. 1. curNode 를 head의 위치로 맞추어준다. 2. head 를 두번째 노드의 주소 값을 가리키도록 한다. 1. curNode , preNode, head 를 첫 번째 노드 값에 집합시킨다. 2. curNode가 6번 노드를 가리키게 하고 target 값인지 확인한다. 3. preNode가 그 다음 노드를 가리킨다. 4. curNode 가 7번 노드를 가리키고 target 값이기 때문에 삭제한다... [단일 연결 리스트 ] 특정 값 노드 검색 4개의 노드 중 특정 노드의 값을 검색하고자 하는 경우의 코드 구현 방법에 대해 알아보자.curNode 가 전체 노드를 순회하고 원하는 노드의 값이 나오면 return, 나오지 않으면 NULL을 반환하면 된다. #include #include typedef struct node { int value; struct node* next;} node;node* head = NULL;node* searchNode(int target) { node* curNode; if (head == NULL) return NULL; //노드가 없으면 NULL 반환 curNode = head; while (curNode != NULL) { if (curNode->value =.. [단일연결 리스트] 전체 노드 삭제 단열 연결 리스트에서 전체 노드를 모두 삭제하는 방법을 그림을 통해서 설명해보겠다. 1. 4개의 노드 중 delNode 삭제할 첫 번째 노드를 가리킨다. 2. delNode 가 첫 번째 노드를 가리키고 있기 때문에 시작 노드를 가리키는 head 는 그 다음 값을 가리키도록 설정한다. 3. 1번 노드 삭제 후 delNode 가 2번 노드를 가리키도록 설정한다. 4. head 가 3번 노드를 가리키도록 설정한다. 5. 2번 노드를 지운 후 delNode 는 3번 노드를 가리킨다. 6. head 가 마지막 4번 노드를 가리킨다. 7. 3번 노드 삭제 후 delNode 는 마지막 4번 노드를 가리킨다. 8. head 는 그 다음 노드를 가리켜야 하는데 노드가 없으니까 아무것도 가리키지 않는 NULL 상태가 .. [단일 연결 리스트] 첫 노드 삭제 첫 노드를 삭제하기 위해 del 이름의 메모리 공간을 할당한다. void delNode() {node* delNode = head; //delNode 에 head 값을 넣음 }만약 연결리스트가 만들어지지 않은 상태이면 삭제할게 없는거니까 함수를 종료한다. if (head == NULL) { return; } 만약 head 가 NULL 이 아닌 경우 head를 그 다음 노드로 옮겨준다. head = head->next; delNode 동적 메모리를 해제해서 첫 번째 노드 5번을 삭제한다. free(delnNode); typedef struct node {int value;struct node* next;}node;node* head = NULL; void delNode() {node* delNode = .. [단일 연결 리스트] 노드 맨 뒤 삽입 노드 맨 앞 삽입과 반대로 새로운 값이 제일 뒤에 붙는 연결 리스트이다. 노드 맨 뒤 삽입은 N만큼의 데이터가 있으면 N만큼 순회를 하기 때문에 O(N)의 시간 복잡도를 가지게 된다. 이를 구현하기 위해서는 일단 내가 연결하고자 하는 노드가 첫 번째 노드인지 아닌지 판별해야 하고 newNode가 NULL을 가리키기 해서 첫 번째 노드와 연결시켜준다. 그 다음 head 가 빈 값이라면 newNode 값을 넣어서 head가 첫번째 노드를 가리키게 한다. typedef struct node{ int value; struct node* next;}node;node* head = NULL; // 초기값을 NULL로 설정void insert_node_rear() { node* newNode; newNode =.. 이전 1 2 3 다음
