C# 자료구조 List, LinkedList, Stack, Queue

장현태입니다·2025년 3월 30일

자료구조

데이터를 효율적인 접근 및 수정을 가능케 하는 자료의
조직, 관리, 저장을 의미
- 데이터 값의 모임, 또 데이터 간의 관계, 그리고
데이터에 적용할 수 있는 함수나 명령을 의미

시간 복잡도

프로그램의 실행부터 완료까지 필요한 과정의 양
알고리즘의 효율성을 결정하는 요소

big-o 표기법

원하는 결과를 출력하기 위해 몇번의 연산을 수행하는지계산하는 방법
알고리즘의 복잡도를 나타내는 점근표기법 데이터 증가량에 따른 시간 증가량을 계산 n개의 데이터가 기준

O(1) : 연산 한번으로 접근 가능한방법
O(n) : 시간의 크기에 따라 올라가는 1차원
O(n^2) : 시간의 크기에 따라 ^2만큼 올라가는 2차원(평면)
O(n^3) : 시간의 크기에 따라 ^3만큼 올라가는 3차원(도형)
O(log n) : 연산에 따라 연산량이 절반이 될 떄 사용
-> 배열 1,2,3,4,5에서 4를 구하기위해 3을 중심으로
적은지 작은지 판별 후 345중에 반을 선택하는 경우

List

한번 크기를 할당하면 정적인 배열이 아닌 크기가 변할 수 있는 동적배열
예를 들어 int형 배열의경우 4byte단위로 메모리에 저장되기 떄문에 인덱스2의 경우 엔덱스0 ~ 인덱스2까지 4바이트 + 4바이트로 8바이트를 연산해 메모리 주소를 찾음 but 배열은 인스턴스를 생성할 때 크기를 정해놓고
데이터를 추가할 수는 없음

//추가 O(n)
list.Add(1); //맨뒤에 추가
list.Insert(1,10) //특정 위치에 추가 그 뒤에있는 인덱스 밀림;
list.Insert(2,2);

//삭제 O(n)
list.Remove(10); //10의 값 찾아서 삭제
list.RemoveAt(2); //인덱스 2의 값 삭제

//접근 O(1)
list[0] = 5; //인덱스 0의 값을 5로 변경

//탐색 O(n)
int index = list.IndexOf(20); //20의 위치 찾기
bool contain = list.Contains(20); //20이 포함되어 있는지

list의 용량 capacity

list의 경우 배열로 이뤄져 있는데 어떻게 늘어남에 따라 배열의 크기가 커지는가 하면 배열의 크기가 커짐에 따라 list자체의 용량을 두배씩 늘려가면서 여유공간을 만드는 방법이다 이떄 용량을 capacity로 지정되는데 capacity의 경우 미리 정해주고 이만큼 사용하겠다라고 지정해주면 두배씩 늘어나는 과정을 없애기 떄문에 효율적인 상황을 만들 수 있다.

list의 연결 종류

단일 연결 리스트, 원형 연결 리스트,
이중 연결 리스트, 원형 이중 연결 리스트

linkedList

node단위로 관리되며 이중 연결 리스트에 해당한다
node에 따라 관리되므로 Index로 관리되지 않는다
그래서 읽기 검색의 경우 O(n)의 시간복잡도 추가,삭제의 경우 O(1)의 사간복잡도를 가진다

LinkedList linkedList = new();
LinkedList node;

linkedList.AddFirst(11);
node = linkedList.AddLast(22);
linkedList.AddLast(33);
linkedList.AddFirst(44);

linkedList.AddAfter(node,55); //노드를 기준으로 그뒤에추가
linkedList.AddBefore(node,66);

linkedList.Remove(node); //노드를 삭제

linkedList.RemoveFirst();
linkedList.RemoveLast();

// 읽기 검색
bool isContain = linkedList.Contains(22);

<LinkedList 시간복잡도>
접근 O(n) 탐색 O(n) 삽입 O(1) 삭제O(1)

<List 시간복잡도>
접근 O(1) 탐색 O(n) 삽입O(n) 삭제O(n)

stack - 후입선출

list의 경우 하나씩 추가, 삭제하여 접근도 인덱스 지정하여 접근가능한 경우라면 stack의 경우 마지막에 추가된 값이먼저 삭제되는 형식으로 박스가 쌓이고 빠지는 형태라 생각하면 된다

Stack stack = new Stack(3);

stack.Push(1);
stack.Push(2); //맨위에 값 넣기 O(1) 하지만 capacity 초과일경우 O(n)

stack.Pop(); // 맨 위의 값 꺼내기 O(1)
stack.Peek(); // 맨위의 값이 어떤건지 확인 O(1)

bool isContain = stack.Contains(1); //1이 포함인지 O(n)

stack.TryPop(out int pop); //있으면 pop 없으면 false
stack.TryPeek(out int peed); //있으면 peek 없으면 false

Queue - 선입선출

먼저 들어온 데이터가 먼저 빠져나오는 형식이다

Queue queue = new Queue();

//시간 복잡도 O(1), capacity가 초과일 경우 O(n)
queue.Enqueue(1);
queue.Enqueue(2);
queue.Enqueue(3);

//O(1)
queue.Dequeue();

//O(1)
queue.Peek();

bool isContain = queue.Contains(2);

첫번째 그림 : Stack
두번쨰 그림 : Queue