Chapter 03~05. 연결리스트(Linked List)

원형 연결 리스트와 양방향 연결 리스트에 대해 알아보겠다.

원형 연결 리스트란 전에 구현 했던 단순 연결 리스트에서 마지막 노드가 NULL을 가리켰는데 이 마지막 노드가 첫번째 노드를 가리키게 하면 이것이 바로 “원형 연결 리스트”가 된다.

#include <stdio.h>
#include <stdlib.h>
#include "CLinkedList.h"

// 단순 연결 리스트의 초기화와 같다.
void ListInit(List * plist)
{
	plist->tail = NULL;
	plist->cur = NULL;
	plist->before = NULL;
	plist->numOfData = 0;
}

// 두 번째 이후의 노드를 머리에 추가
void LInsertFront(List * plist, Data data)
{
	Node * newNode = (Node*)malloc(sizeof(Node)); // 새 노드 생성
	newNode->data = data; // 새 노드에 데이터 저장

	if(plist->tail == NULL) // 첫 번째 노드라면,
	{
		plist->tail = newNode; // tail 이 새 노드를 가리키게 한다
		newNode->next = newNode; // 새 노드 자신을 가리키게 한다.
	}
	else // 두 번쨰 이후의 노드라면
	{
		newNode->next = plist->tail->next; // 새 노드와 다음 노드를 연결한다.
		plist->tail->next = newNode; // 새 노드와 tail에 있는 노드를 연결한다.
	}

	(plist->numOfData)++; // 데이터의 수를 알려주는 변수 1증가
}

// 두 번째 이후의 노드를 tail 에 추가
void LInsert(List * plist, Data data)
{
	Node * newNode = (Node*)malloc(sizeof(Node));
	newNode->data = data;

	if(plist->tail == NULL) 
	{
		plist->tail = newNode;
		newNode->next = newNode;
	}
	else 
	{
		newNode->next = plist->tail->next;
		plist->tail->next = newNode;
		plist->tail = newNode; // LInsertFront 함수와의 유일한 차이점
	}

	(plist->numOfData)++;
}

// cur과 before 의 역할이 단순 연결 리스트와 동일하므로 cur이 가리키는 노드의 데이터를 반환하면 됨
int LFirst(List * plist, Data * pdata)
{
	if(plist->tail == NULL)   // 저장된 노드가 없다면 false 반환
		return FALSE;

	plist->before = plist->tail; // before이 꼬리를 가리키게 한다.
	plist->cur = plist->tail->next; // cur이 머리를 가리키게 한다.

	*pdata = plist->cur->data; // cur이 가리키는 노드의 데이터 반환
	return TRUE; 
}

// cur과 before을 한 칸씩 다음 노드로 이동시켜야 한다.
int LNext(List * plist, Data * pdata)
{
	if(plist->tail == NULL)   
		return FALSE;

	plist->before = plist->cur; // LFirst 함수에서 tail 이 cur로만 바뀜
	plist->cur = plist->cur->next;  // LFirst 함수에서 tail 이 cur로만 바뀜

	*pdata = plist->cur->data;
	return TRUE;
}

// 단순 연결리스트와 동일한 방식을 사용하지만, 예외적인 상황 2가지를 고려해야 함.
// 예외적인 상황 2가지는 아래 주석 처리 되어 있는 부분임.
Data LRemove(List * plist)
{
	Node * rpos = plist->cur;
	Data rdata = rpos->data;

	if(rpos == plist->tail)    // 삭제 대상을 tail이 가리킨다면
	{
		if(plist->tail == plist->tail->next)    // 그리고 마지막 남은 노드라면
			plist->tail = NULL;
		else
			plist->tail = plist->before;
	}

	plist->before->next = plist->cur->next;
	plist->cur = plist->before;

	free(rpos);
	(plist->numOfData)--;
	return rdata;
}

int LCount(List * plist)
{
	return plist->numOfData;
}

위의 코드는 원형 연결 리스트를 구현한 코드이다.

양방향 연결 리스트는 노드가 양쪽 방향으로 연결된 구조의 리스트이다. 즉 왼쪽 노드가 오른쪽 노드를 가리킴과 동시에 오른쪽 노드도 왼쪽 노드를 가리키는 구조이다.

따라서 양방향 연결 리스트의 노드를 표현하는 구조체는 다음과 같이 정의된다.

코드트리 기초문제 중 반복문 활용 - 별표 출력하기 10
반복문 활용하는 문제로 푸는데 생각보다 오래 걸렸다,,


이 문제인데 n이 홀수인 경우와 짝수인 경우, 반복문안에 조건문을 활용해서 코드를 구현했는데 아마 분명 더 좋게 짤 수 있을꺼 같은데 아직 생각해내지 못했다.

#include <iostream>
using namespace std;
int main() {
    // 여기에 코드를 작성해주세요.
    int a; cin >> a;
    if(a % 2 == 1){
        for(int i = 0; i < a; i++){
            if(i % 2 == 0){
                for(int j = 0; j < (i+1) / 2 + 1; j++){
                    cout << "* ";
                }
                cout << '\n';
            }
            else{
                for(int j = 0; j < a - i/2; j++){
                    cout << "* ";
                }
                cout << '\n';
            }
        }
        for(int i = 0; i < a; i++){
            if(i % 2 == 0){
                for(int j = 0; j < (a - i) / 2 + 1; j++){
                    cout << "* ";
                }
                cout << '\n';
            }
            else{
                for(int j = 0; j < (a + i) / 2 + 1; j++){
                    cout << "* ";
                }
                cout << '\n';
            }
        }
    }
    if(a % 2 == 0){
        for(int i = 0; i < a; i++){
            if(i % 2 == 0){
                for(int j = 0; j < (i+1) / 2 + 1; j++){
                    cout << "* ";
                }
                cout << '\n';
            }
            else{
                for(int j = 0; j < a - i/2; j++){
                    cout << "* ";
                }
                cout << '\n';
            }
        }
        for(int i = 0; i < a; i++){
            if(i % 2 == 0){
                for(int j = 0; j < (a + i) / 2 + 1; j++){
                    cout << "* ";
                }
                cout << '\n';
            }
            else{
                for(int j = 0; j < (a - i) / 2 + 1; j++){
                    cout << "* ";
                }
                cout << '\n';
            }
        }
    }
    return 0;
}

우선 나는 이렇게 짯고 제출해서 통과했는데 해설을 보니

#include <iostream>

using namespace std;

int main() {
    // 변수 선언 및 입력
    int n;
    cin >> n;
	
	// i가 짝수인 경우 별을 1개, 홀수인 경우 i + 1개 출력합니다
	for(int i = 0; i < 2 * n; i++) {
		if(i % 2 == 0) {
			for(int k = 0; k < 1 + i / 2; k++)
				cout << "* ";
		}
		else {
			for(int k = 0; k < n - (i - 1) / 2; k++)
				cout << "* ";
		}
		cout << endl;
	}

    return 0;
}

이렇게나 간단하게 구현하면 되는 문제였다,, 생각을 좀 더 해보면서 코드를 작성해야 할 꺼 같다.