List(연결리스트)

연결리스트는 랜덤 접근이 가능한 배열과는 다른 순차적인(sequential) 자료구조입니다.

연결리스트는 노드들로 구성되어 있습니다. 노드는 저장할 값과 다음 노드를 가리키는 포인터로 이루어져 있습니다. 연결리스트의 첫 노드인 헤드(Head)로 부터 노드에 다음 노드를 가리키는 포인터를 사용해 리스트를 순회할 수 있게 됩니다.

<List>

위와 같은 연결리스트를 Singly Linked List라고 합니다.

Singly Linked List의 각 노드에 이전 노드를 가리키는 포인터를 추가하게 되면 양방향으로 순회가 가능한 Doubly Linked List가 되고, 환형 큐(Circular Queue)와 같이 연결리스트의 마지막 노드인 테일(Tail)과 헤드를 이으면 Circular Linked List가 됩니다.

<Doubly Linked List>

각 노드는 저장할 값과 자신의 앞, 뒤 노드를 가리키는 포인터를 가짐

<Circular Linked List>

테일의 포인터는 헤드를 가리킴

두 자료구조의 장단점을 나열해보자면, 배열은 인덱스로 인한 무작위 접근이 가능하고, 리스트에 비해 저장공간을 적게 필요로 하지만, 리스트에 비해 자료의 삽입, 삭제가 비효율 적인 부분이 있습니다. 순서를 유지하면서 자료를 삽입 / 삭제하기 위해서는 최악의 경우 모든 데이터를 옮겨주어야 하기 때문입니다.

리스트는 무작위 접근이 불가능하므로 무조건 순차적으로 탐색해야 하며, 노드에 저장할 값과 포인터를 포함하고 있기 때문에 똑같은 크기의 배열에 비해 저장공간을 많이 차지하게 되지만, 자료의 삽입과 삭제가 새로운 노드를 만들어 포인터로 이어주기만 하면 되기 때문에 간편하고 유연하게 동작합니다.

	List(연결리스트)	동적배열
Indexing	O(N)	O(1)
Insert / Delete at beginning	O(1)	O(N)
Insert / Delete at end	O(1) when last element is known; O(N) when last element is unknown	O(1)
Insert / Delete in middle	search time + O(1)	O(N)

리스트와 배열의 시간복잡도 비교,https://en.wikipedia.org/wiki/Linked_list

아래 코드는 리스트를 구현한 코드입니다.

C++

#include <stdio.h>
#include <list>
using namespace std;

int main() {
    int n;
    scanf("%d", &n);

    list<int> mylist;
    while(n--) {
        char command[10];
        scanf("%s", command);

        // push, get, size, count, clear
        if(command[0] == 'p') {
            int value;
            scanf("%d", &value);
            mylist.push_back(value);
        } else if(command[0] == 'g') {
            int idx;
            scanf("%d", &idx);
            list<int>::iterator it = mylist.begin();
            while(idx--) {
                it++;
            }
            printf("%d\n", *it);
        } else if(command[0] == 's') {
            printf("%d\n", mylist.size());
        } else if(command[1] == 'o') {
            int target, cnt = 0;
            scanf("%d", &target);
            for(list<int>::iterator it = mylist.begin(); it != mylist.end(); it++) {
                if(*it == target) {
                    cnt++;
                }
            }
            printf("%d\n", cnt);
        } else {
            mylist.clear();
        }
    }

    return 0;
}

Java

import java.util.*;

public class Main {
    public static void main(String args[]) {
        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            String command = scanner.next();

            // push, get, size, count, clear
            if (command.charAt(0) == 'p') {
                int value = scanner.nextInt();
                list.add(value);
            }
            else if (command.charAt(0) == 'g') {
                int idx = scanner.nextInt();
                System.out.println(list.get(idx));
            }
            else if (command.charAt(0) == 's') {
                System.out.println(list.size());
            }
            else if (command.charAt(1) == 'o') {
                int target = scanner.nextInt(), count = 0;
                for (int j = 0; j < list.size(); j++) {
                    if (list.get(j) == target) {
                        count++;
                    }
                }
                System.out.println(count);
            }
            else {
                list.clear();
            }
        }
    }
}

다음엔 큐에 대해 알아보겠습니다.