Solidity 로 연결 리스트 구현하기

Solidity는 기본적으로 배열(array)과 mapping(map)은 제공하지만,
✅ linked list 자료구조는 제공하지 않습니다.
→ 따라서 직접 구현해야 합니다.

⸻

🧩 왜 Solidity는 Linked List를 제공하지 않을까?
• EVM의 storage 구조가 랜덤 접근 기반이기 때문에
→ 연속된 메모리보다 keccak256(slot) 방식의 mapping 기반 인덱싱이 더 유리합니다.
• Solidity의 gas 비용 구조상, linked list는 효율적이지 않은 경우가 많습니다.
• 그래도 👇 순차적 삽입/삭제가 필요한 경우엔 여전히 유용합니다.

⸻

✅ 예제1: 단일 연결 리스트 (Singly Linked List)

아래는 Solidity로 구현한 간단한 Singly Linked List 예제입니다.

⸻

🔧 Solidity 코드 (0.8.x 이상)

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.20;

contract LinkedList {
    struct Node {
        uint data;
        uint next;
        bool exists;
    }

    mapping(uint => Node) public nodes;
    uint public head;
    uint public length;
    uint private idCounter;

    constructor() {
        head = 0; // 초기에는 0이 head (0은 dummy head 역할)
        nodes[head] = Node({ data: 0, next: 0, exists: true });
        idCounter = 1;
    }

    /// @notice 리스트 끝에 추가
    function append(uint _data) external {
        uint current = head;
        while (nodes[current].next != 0) {
            current = nodes[current].next;
        }

        uint newId = idCounter++;
        nodes[newId] = Node({ data: _data, next: 0, exists: true });
        nodes[current].next = newId;
        length++;
    }

    /// @notice 특정 노드 ID 기준으로 삭제 (head는 삭제 불가)
    function remove(uint id) external {
        require(id != head, "cannot remove dummy head");
        require(nodes[id].exists, "node not exists");

        uint prev = head;
        while (nodes[prev].next != id && nodes[prev].next != 0) {
            prev = nodes[prev].next;
        }
        require(nodes[prev].next == id, "node not found");

        nodes[prev].next = nodes[id].next;
        delete nodes[id];
        length--;
    }

    /// @notice 전체 리스트 조회
    function getAll() external view returns (uint[] memory) {
        uint[] memory result = new uint[](length);
        uint current = nodes[head].next;
        uint i = 0;
        while (current != 0) {
            result[i++] = nodes[current].data;
            current = nodes[current].next;
        }
        return result;
    }
}

⸻

📌 핵심 설명

요소	설명
mapping(uint => Node)	노드를 ID로 저장 (linked list의 key 역할)
Node 구조체	data, next, exists 필드 포함
head	항상 0번 노드 (dummy head)
idCounter	노드마다 고유한 ID 부여

⸻

✅ 사용 예시
1. append(100) → 노드 추가
2. getAll() → [100]
3. append(200) → [100, 200]
4. remove(1) → [200] (ID 1번 노드 삭제)

⸻

🧠 추가 팁
• 양방향 리스트도 구현 가능: prev 필드를 추가하면 됩니다
• LinkedListLib로 만들면 재사용 가능
• 메모리 구조와 storage 구조를 구분해서 설계하세요

⸻

✅ 예제2: 단일/양방향/Enumable(반복가능한) 연결 리스트

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.20;

/**
 * ✅ Singly Linked List
 */
contract SinglyLinkedList {
    struct Node {
        uint data;
        uint next;
        bool exists;
    }

    mapping(uint => Node) public nodes;
    uint public head;
    uint public length;
    uint private idCounter;

    constructor() {
        head = 0; // dummy head
        nodes[head] = Node({ data: 0, next: 0, exists: true });
        idCounter = 1;
    }

    function append(uint _data) external {
        uint current = head;
        while (nodes[current].next != 0) {
            current = nodes[current].next;
        }

        uint newId = idCounter++;
        nodes[newId] = Node({ data: _data, next: 0, exists: true });
        nodes[current].next = newId;
        length++;
    }

    function remove(uint id) external {
        require(id != head, "cannot remove head");
        require(nodes[id].exists, "not found");

        uint prev = head;
        while (nodes[prev].next != id && nodes[prev].next != 0) {
            prev = nodes[prev].next;
        }
        require(nodes[prev].next == id, "not found");

        nodes[prev].next = nodes[id].next;
        delete nodes[id];
        length--;
    }

    function getAll() external view returns (uint[] memory) {
        uint[] memory result = new uint[](length);
        uint current = nodes[head].next;
        uint i = 0;
        while (current != 0) {
            result[i++] = nodes[current].data;
            current = nodes[current].next;
        }
        return result;
    }
}

/**
 * ✅ Doubly Linked List
 */
contract DoublyLinkedList {
    struct Node {
        uint data;
        uint next;
        uint prev;
        bool exists;
    }

    mapping(uint => Node) public nodes;
    uint public head;
    uint public tail;
    uint public length;
    uint private idCounter;

    constructor() {
        head = 0;
        tail = 0;
        idCounter = 1;
    }

    function append(uint _data) external {
        uint newId = idCounter++;
        nodes[newId] = Node({ data: _data, next: 0, prev: tail, exists: true });

        if (length == 0) {
            head = newId;
        } else {
            nodes[tail].next = newId;
        }

        tail = newId;
        length++;
    }

    function remove(uint id) external {
        require(nodes[id].exists, "not found");

        if (nodes[id].prev != 0) {
            nodes[nodes[id].prev].next = nodes[id].next;
        } else {
            head = nodes[id].next;
        }

        if (nodes[id].next != 0) {
            nodes[nodes[id].next].prev = nodes[id].prev;
        } else {
            tail = nodes[id].prev;
        }

        delete nodes[id];
        length--;
    }

    function getAllForward() external view returns (uint[] memory) {
        uint[] memory result = new uint[](length);
        uint current = head;
        uint i = 0;
        while (current != 0) {
            result[i++] = nodes[current].data;
            current = nodes[current].next;
        }
        return result;
    }

    function getAllBackward() external view returns (uint[] memory) {
        uint[] memory result = new uint[](length);
        uint current = tail;
        uint i = 0;
        while (current != 0) {
            result[i++] = nodes[current].data;
            current = nodes[current].prev;
        }
        return result;
    }
}

/**
 * ✅ Enumerable Iterable Linked List (Mapping + Array)
 */
contract EnumerableList {
    struct Item {
        uint data;
        bool exists;
    }

    mapping(uint => Item) public items;
    uint[] public keys;

    function add(uint key, uint value) external {
        require(!items[key].exists, "already exists");
        items[key] = Item({ data: value, exists: true });
        keys.push(key);
    }

    function remove(uint key) external {
        require(items[key].exists, "not exists");
        delete items[key];
        for (uint i = 0; i < keys.length; i++) {
            if (keys[i] == key) {
                keys[i] = keys[keys.length - 1];
                keys.pop();
                break;
            }
        }
    }

    function getAll() external view returns (uint[] memory values) {
        uint count = 0;
        for (uint i = 0; i < keys.length; i++) {
            if (items[keys[i]].exists) count++;
        }

        values = new uint[](count);
        uint j = 0;
        for (uint i = 0; i < keys.length; i++) {
            if (items[keys[i]].exists) {
                values[j++] = items[keys[i]].data;
            }
        }
    }
}