단일 연결 리스트를 이용한 FIFO 구현

4/11/2023
20 minutes to read

이 글에서는 여러 프로그래밍 언어를 사용하여 단일 연결 리스트(Singly Linked List)를 이용한 FIFO(First In First Out) 구현 방법을 소개합니다. 단일 연결 리스트는 배열에 비해 데이터의 삽입과 삭제가 용이한 데이터 구조로, 각 노드가 다음 노드를 가리키는 포인터를 포함합니다. 이를 통해 간단한 FIFO 구현을 살펴볼 것이며, 사용자로부터 이름과 전화번호를 입력 받아 리스트에 저장하고, 리스트를 순회하며 입력된 데이터를 출력하는 과정을 다룰 것입니다. 이 글에서는 C, C++, C#, Java, Python, JavaScript, TypeScript, Go, Rust 등 다양한 프로그래밍 언어로 예제를 제공하여, 언어별 차이를 이해하고 해당 언어의 구현 방식을 학습할 수 있습니다.

단일 연결 리스트를 이용한 FIFO 구현 (C# 버전)

이 코드 예제에서는 C# 프로그래밍 언어를 사용하여 단일 연결 리스트(Singly Linked List)를 이용한 FIFO(First In First Out) 구현 방법을 살펴보겠습니다.

구조체와 메소드 정의

먼저, 노드를 구성할 클래스인 Node를 정의합니다.

public class Node
{
    public string Name;          // 이름
    public string Phone;         // 전화번호
    public Node NextNode;  // 다음 노드를 가리키는 포인터
}

메인 함수

메인 함수는 다음과 같이 작성되었습니다.

using System;

class MainClass
{
    public static void Main(string[] args)
    {
        int i;               // 반복용
        Node head = null;   // 첫 번째 노드
        Node current;       // 새롭게 추가되는 현재 노드

        Console.WriteLine("데이터 입력:");

        // 노드 추가
        for (i = 0; i < 3; i++)
        {
            current = new Node();                // 새 노드 생성
            string[] input = Console.ReadLine().Split(' ');
            current.Name = input[0]; // 값 대입
            current.Phone = input[1]; // 값 대입
            current.NextNode = head;           // 새 노드의 포인터에 첫번째 노드 지정
            head = current;                     // 새 노드를 첫번째 노드로 설정
        }

        Console.WriteLine("데이터 출력:");

        // 노드 출력
        current = head;
        while (current != null)
        {
            Console.WriteLine("{0} {1}", current.Name, current.Phone);
            current = current.NextNode;
        }
    }
}

이 예제에서는 사용자로부터 이름과 전화번호를 입력 받아 단일 연결 리스트에 저장하고, 리스트를 순회하며 입력된 데이터를 출력하는 과정을 보여줍니다. 이를 통해 단일 연결 리스트를 이용한 간단한 FIFO 구현 방법을 이해할 수 있습니다.

단일 연결 리스트를 이용한 FIFO 구현

이 코드 예제에서는 C 프로그래밍 언어를 사용하여 단일 연결 리스트(Singly Linked List)를 이용한 FIFO(First In First Out) 구현 방법을 살펴보겠습니다.

구조체와 함수 정의

먼저, 노드를 구성할 구조체인 Node를 정의합니다.

typedef struct Node {
    char Name[20];          // 이름
    char Phone[20];         // 전화번호
    struct Node* NextNode;  // 다음 노드를 가리키는 포인터
} Node;

그 다음으로는 메모리 할당을 위한 GetNode() 함수를 정의합니다.

Node* GetNode(void)
{
    return (Node*)malloc(sizeof(Node));
}

메인 함수

메인 함수는 다음과 같이 작성되었습니다.

int main(void)
{
    int i;               // 반복용
    Node* head = NULL;   // 첫 번째 노드
    Node* current;       // 새롭게 추가되는 현재 노드

    printf("데이터 입력:\n");

    // 노드 추가
    for (i = 0; i < 3; i++) {
        current = GetNode();                // 새 노드 생성
        scanf("%s %s", current->Name, current->Phone); // 값 대입
        current->NextNode = head;           // 새 노드의 포인터에 첫번째 노드 지정
        head = current;                     // 새 노드를 첫번째 노드로 설정
    }

    printf("데이터 출력:\n");

    // 노드 출력
    current = head;
    while (current != NULL) {
        printf("%s %s\n", current->Name, current->Phone);
        current = current->NextNode;
    }

    // 메모리 해제
    current = head;
    while (current != NULL) {
        Node* next = current->NextNode;
        free(current);
        current = next;
    }

    return 0;
}

전체 소스는 다음과 같습니다.

// singly_linked_list_fifo.c

/*
    리스트(List) : 배열에 비해서 데이터의 입력과 삭제가 용이한 데이터 구조
    (입력한 순서와 반대로 구성된 리스트 작성)
*/
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

// 단일 링크드 리스트용 구조체
typedef struct Node {
    char Name[20];          // 이름
    char Phone[20];         // 전화번호
    struct Node* NextNode;  // 다음 노드를 가리키는 포인터
} Node;

Node* GetNode(void);

// 메인 함수
int main(void)
{
    int i;               // 반복용
    Node* head = NULL;   // 첫 번째 노드
    Node* current;       // 새롭게 추가되는 현재 노드

    printf("데이터 입력:\n");

    // 노드 추가
    for (i = 0; i < 3; i++) {
        current = GetNode();                // 새 노드 생성
        scanf("%s %s", current->Name, current->Phone); // 값 대입
        current->NextNode = head;           // 새 노드의 포인터에 첫번째 노드 지정
        head = current;                     // 새 노드를 첫번째 노드로 설정
    }

    printf("데이터 출력:\n");

    // 노드 출력
    current = head;
    while (current != NULL) {
        printf("%s %s\n", current->Name, current->Phone);
        current = current->NextNode;
    }

    // 메모리 해제
    current = head;
    while (current != NULL) {
        Node* next = current->NextNode;
        free(current);
        current = next;
    }

    return 0;
}

// 메모리 할당 함수
Node* GetNode(void)
{
    return (Node*)malloc(sizeof(Node));
}

데이터 입력:
병원 119
경찰 112
전화 114
데이터 출력:
전화 114
경찰 112
병원 119

이 예제에서는 사용자로부터 이름과 전화번호를 입력 받아 단일 연결 리스트에 저장하고, 리스트를 순회하며 입력된 데이터를 출력한 다음 메모리를 해제하는 과정을 보여줍니다. 이를 통해 단일 연결 리스트를 이용한 간단한 FIFO 구현 방법을 이해할 수 있습니다.

단일 연결 리스트를 이용한 FIFO 구현 (Java 버전)

이 코드 예제에서는 Java 프로그래밍 언어를 사용하여 단일 연결 리스트(Singly Linked List)를 이용한 FIFO(First In First Out) 구현 방법을 살펴보겠습니다.

클래스와 메소드 정의

먼저, 노드를 구성할 클래스인 Node를 정의합니다.

public class Node {
    String name;          // 이름
    String phone;         // 전화번호
    Node nextNode;  // 다음 노드를 가리키는 포인터
}

메인 클래스

메인 클래스는 다음과 같이 작성되었습니다.

import java.util.Scanner;

public class SinglyLinkedListFIFO {
    public static void main(String[] args) {
        int i;               // 반복용
        Node head = null;   // 첫 번째 노드
        Node current;       // 새롭게 추가되는 현재 노드

        Scanner scanner = new Scanner(System.in);

        System.out.println("데이터 입력:");

        // 노드 추가
        for (i = 0; i < 3; i++) {
            current = new Node();                // 새 노드 생성
            String[] input = scanner.nextLine().split(" ");
            current.name = input[0]; // 값 대입
            current.phone = input[1]; // 값 대입
            current.nextNode = head;           // 새 노드의 포인터에 첫번째 노드 지정
            head = current;                     // 새 노드를 첫번째 노드로 설정
        }

        System.out.println("데이터 출력:");

        // 노드 출력
        current = head;
        while (current != null) {
            System.out.printf("%s %s%n", current.name, current.phone);
            current = current.nextNode;
        }

        scanner.close();
    }
}

단일 연결 리스트를 이용한 FIFO 구현 (Python 버전)

이 코드 예제에서는 Python 프로그래밍 언어를 사용하여 단일 연결 리스트(Singly Linked List)를 이용한 FIFO(First In First Out) 구현 방법을 살펴보겠습니다.

클래스 정의

먼저, 노드를 구성할 클래스인 Node를 정의합니다.

class Node:
    def __init__(self, name=None, phone=None, next_node=None):
        self.name = name        # 이름
        self.phone = phone      # 전화번호
        self.next_node = next_node  # 다음 노드를 가리키는 포인터

메인 코드

메인 코드는 다음과 같이 작성되었습니다.

if __name__ == "__main__":
    head = None  # 첫 번째 노드
    current = None  # 새롭게 추가되는 현재 노드

    print("데이터 입력:")

    # 노드 추가
    for _ in range(3):
        name, phone = input().split()
        current = Node(name, phone, head)  # 새 노드 생성 및 값 대입
        head = current  # 새 노드를 첫 번째 노드로 설정

    print("데이터 출력:")

    # 노드 출력
    current = head
    while current is not None:
        print(f"{current.name} {current.phone}")
        current = current.next_node

단일 연결 리스트를 이용한 FIFO 구현 (JavaScript 버전)

이 코드 예제에서는 JavaScript 프로그래밍 언어를 사용하여 단일 연결 리스트(Singly Linked List)를 이용한 FIFO(First In First Out) 구현 방법을 살펴보겠습니다.

클래스 정의

먼저, 노드를 구성할 클래스인 Node를 정의합니다.

class Node {
    constructor(name, phone, nextNode = null) {
        this.name = name;          // 이름
        this.phone = phone;         // 전화번호
        this.nextNode = nextNode;  // 다음 노드를 가리키는 포인터
    }
}

메인 코드

메인 코드는 다음과 같이 작성되었습니다.

(async () => {
    let head = null;   // 첫 번째 노드
    let current;       // 새롭게 추가되는 현재 노드

    console.log("데이터 입력:");

    // 노드 추가
    for (let i = 0; i < 3; i++) {
        let input = (await readLine()).split(' ');
        current = new Node(input[0], input[1], head); // 새 노드 생성 및 값 대입
        head = current; // 새 노드를 첫 번째 노드로 설정
    }

    console.log("데이터 출력:");

    // 노드 출력
    current = head;
    while (current !== null) {
        console.log(`${current.name} ${current.phone}`);
        current = current.nextNode;
    }
})();

function readLine() {
    const readline = require('readline');
    const rl = readline.createInterface({
        input: process.stdin,
        output: process.stdout
    });

    return new Promise(resolve =>
        rl.question('', ans => {
            rl.close();
            resolve(ans);
        })
    );
}

단일 연결 리스트를 이용한 FIFO 구현 (C++ 버전)

이 코드 예제에서는 C++ 프로그래밍 언어를 사용하여 단일 연결 리스트(Singly Linked List)를 이용한 FIFO(First In First Out) 구현 방법을 살펴보겠습니다.

클래스 정의

먼저, 노드를 구성할 클래스인 Node를 정의합니다.

#include <iostream>
#include <string>

class Node {
public:
    std::string name;          // 이름
    std::string phone;         // 전화번호
    Node* nextNode;            // 다음 노드를 가리키는 포인터

    Node(const std::string& name, const std::string& phone, Node* nextNode = nullptr)
        : name(name), phone(phone), nextNode(nextNode) {}
};

메인 코드

메인 코드는 다음과 같이 작성되었습니다.

int main() {
    Node* head = nullptr;   // 첫 번째 노드
    Node* current;          // 새롭게 추가되는 현재 노드

    std::cout << "데이터 입력:\n";

    // 노드 추가
    for (int i = 0; i < 3; i++) {
        std::string name, phone;
        std::cin >> name >> phone;
        current = new Node(name, phone, head); // 새 노드 생성 및 값 대입
        head = current;                        // 새 노드를 첫 번째 노드로 설정
    }

    std::cout << "데이터 출력:\n";

    // 노드 출력
    current = head;
    while (current != nullptr) {
        std::cout << current->name << " " << current->phone << std::endl;
        current = current->nextNode;
    }

    // 메모리 해제
    current = head;
    while (current != nullptr) {
        Node* next = current->nextNode;
        delete current;
        current = next;
    }

    return 0;
}

단일 연결 리스트를 이용한 FIFO 구현 (Go 버전)

이 코드 예제에서는 Go 프로그래밍 언어를 사용하여 단일 연결 리스트(Singly Linked List)를 이용한 FIFO(First In First Out) 구현 방법을 살펴보겠습니다.

구조체 정의

먼저, 노드를 구성할 구조체인 Node를 정의합니다.

type Node struct {
    name      string
    phone     string
    nextNode  *Node
}

메인 코드

메인 코드는 다음과 같이 작성되었습니다.

package main

import (
    "fmt"
    "strings"
)

func main() {
    var head *Node = nil // 첫 번째 노드
    var current *Node    // 새롭게 추가되는 현재 노드

    fmt.Println("데이터 입력:")

    // 노드 추가
    for i := 0; i < 3; i++ {
        var name, phone string
        fmt.Scan(&name, &phone)
        current = &Node{name: name, phone: phone, nextNode: head} // 새 노드 생성 및 값 대입
        head = current // 새 노드를 첫 번째 노드로 설정
    }

    fmt.Println("데이터 출력:")

    // 노드 출력
    current = head
    for current != nil {
        fmt.Println(current.name, current.phone)
        current = current.nextNode
    }
}

단일 연결 리스트를 이용한 FIFO 구현 (Rust 버전)

이 코드 예제에서는 Rust 프로그래밍 언어를 사용하여 단일 연결 리스트(Singly Linked List)를 이용한 FIFO(First In First Out) 구현 방법을 살펴보겠습니다.

구조체 정의

먼저, 노드를 구성할 구조체인 Node와 리스트를 관리할 구조체인 List를 정의합니다.

use std::io;
use std::ptr;

struct Node {
    name: String,
    phone: String,
    next_node: *mut Node,
}

struct List {
    head: *mut Node,
}

메인 코드

메인 코드는 다음과 같이 작성되었습니다.

fn main() {
    let mut list = List { head: ptr::null_mut() };

    println!("데이터 입력:");

    // 노드 추가
    for _ in 0..3 {
        let mut name = String::new();
        let mut phone = String::new();

        io::stdin().read_line(&mut name).unwrap();
        io::stdin().read_line(&mut phone).unwrap();

        let name = name.trim().to_string();
        let phone = phone.trim().to_string();

        let node = Box::new(Node {
            name: name.clone(),
            phone: phone.clone(),
            next_node: list.head,
        });

        list.head = Box::into_raw(node);
    }

    println!("데이터 출력:");

    // 노드 출력
    let mut current = list.head;
    while !current.is_null() {
        let node = unsafe { &*current };
        println!("{} {}", node.name, node.phone);
        current = node.next_node;
    }

    // 메모리 해제
    while !list.head.is_null() {
        let node = unsafe { Box::from_raw(list.head) };
        list.head = node.next_node;
    }
}

단일 연결 리스트를 이용한 FIFO 구현 (TypeScript 버전)

이 코드 예제에서는 TypeScript 프로그래밍 언어를 사용하여 단일 연결 리스트(Singly Linked List)를 이용한 FIFO(First In First Out) 구현 방법을 살펴보겠습니다.

인터페이스 및 클래스 정의

먼저, 노드를 구성할 인터페이스인 Node와 리스트를 관리할 클래스인 LinkedList를 정의합니다.

interface Node {
  name: string;
  phone: string;
  nextNode: Node | null;
}

class LinkedList {
  head: Node | null;

  constructor() {
    this.head = null;
  }
}

메인 코드

메인 코드는 다음과 같이 작성되었습니다.

import * as readline from 'readline';

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout
});

const list = new LinkedList();

console.log('데이터 입력:');

// 노드 추가
const readData = (count: number) => {
  if (count === 0) {
    displayData();
    return;
  }

  rl.question('이름 전화번호 입력: ', (input: string) => {
    const [name, phone] = input.split(' ');
    const newNode: Node = { name, phone, nextNode: list.head };
    list.head = newNode;
    readData(count - 1);
  });
};

readData(3);

// 노드 출력
function displayData() {
  console.log('데이터 출력:');

  let current = list.head;
  while (current !== null) {
    console.log(`${current.name} ${current.phone}`);
    current = current.nextNode;
  }

  rl.close();
}