#25 [C 자료구조] 리스트 개념: 가장 많이 쓰이는 선형 자료형

파-하! (파이리썬에 얼떨결에 구글링 해서 들어온 사람들 하이라는 뜻)

오늘은 리스트에 대해서 알아볼 것이다.

리스트는 그 모오오오오든 자료구조형에서 가장 많이 쓰이고 종류도 더럽게 많은 자료형이다.

기억 날지 모르겠지만 아래의 자료형 그래프를 보자.

 

자료구조	단순구조 (Simple)	정수(int)
		실수(float, double)
		문자열(char)
	선형구조 (Linear)	리스트(List)	선형리스트
			연결리스트
		스택(Stack)
		큐(Queue)
		데크(DeQue)
	비선형구조 (Non-Linear)	트리(Tree)	일반 트리
			이진 트리
		그래프(Graph)	방향 그래프
			무방향 그래프
	파일 구조 (File Organization)	순차파일
		색인파일
		직접파일

 

다른 언어 혹은 C언어를 깊이 공부해본 사람이라면 리스트가 가장 활용도가 높고 다양하게 쓰인다는 것을 알 수 있다. 리스트엔 배열 리스트, 연결 리스트, 단순 연결 리스트, 연결 리스트로 구현한 스택^-^/큐^3^/덱^0^, 원형 연결 리스트, 이중 연결 리스트와 같은 것들이 있고 또 각 리스트마다 동적 메모리 할당 방법이 다르다! 얏호우!

신나는 리스트를 차근차근 모조리 씹어먹어 주마 배워나가 보자!!

 

하하하하하리스트신나하하하하하

 

---

 

 

 

배열 리스트(Array List)

가장 직관적이고 단순한 방법이다. 지금 까지 배웠던 배열의 원래 이름이 배열 리스트라 보면 된다.

- 논리적 순서와 물리적 저장 순서가 동일하다.

- 메모리상에 순차적을 저장된다는 말씀!

- 메모리상 거리도 동일하다. 이게 무슨 말이냐?

* 원형 큐를 나눠주는 이유는 n이 넘어가면 다시 돌기 때문

배열 리스트 종류

- 문자열 리스트 (마지막 문자는 \0라는 점)

- 행렬

- 다항식

 

배열 리스트 장단점

- 장점

구현 핵간단

원소 접근이나 삽입/삭제할 때 적합

 

- 단점

항목 개수가 제한됨

삽입/삭제 시 순서를 유지하기 위한 오버헤드(원소의 이동)가 많다

i.e. k번 째 원소 삽입/삭제 시 k+1~n / k~n-1 번 원소이동 --> n-k-1개 이동

---

 

 

 

연결 리스트(Linked List)

연결 리스트는 배열 리스트의 단점을 보완하기 위해 만들어졌다.

다음과 같은 큰 특징을 지닌다.

- 각 원소들이 메모리 내 어떤 곳에 위치하든 노상관, 순서 노상관

- 하지만 순서대로 접근하기 위해 {Value, Link} 순으로 저장하여 Link에 순서상 다음 Value의 주소 값(위치)을 저장함

- 따라서 {Value, Link}는 구조체 형식을 띔

- 마지막 요소는 Link에 NULL 저장

순서 따윈 어떻게 되든!

연결 리스트에 삽입하기

연결 리스트에 새로운 데이터를 삽입... 삽입해보자.

여기서 5번 메모리 칸에다가 {Gat}를 삽입하고 Fat과 Hat 사이에 넣어보자.

순서도 모양으로 처리하자면 다음과 같이 될 것이다.

1) MALLOC() 함수를 통해 사용하지 않는 노드 a를 가져온다.

2) 노드 a의 데이터 필드에 Gat를 대입한다.

3) a의 Link필드가 Fat 다음 노드를 가리키도록 한다.

4) Fat의 노드가 Gat의 노드를 가르키도록 한다.

 

여기서 순서가 굉장히 중요한데, 이전 참조항인 Fat을 먼저 끊어내면 일시에 전체 연결 리스트가 끊어지게 된다. 따라서 Gat을 먼저 Hat에 연결하고 Fat을 도킹하는 것이다.

 

연결 리스트 삭제하기

삭제하기 또한 오류가 안 나게 이전 참조인 Fat의 링크를 Hat 노드에 연결시켜주고 나서 Gat 노드를 삭제하는 방향으로 진행한다.

 

연결 리스트 장단점

- 장점

• 배열 리스트와 달리 최대 원소수가 고정되지 않음
• 삽입/삭제 굿
• 포인터만 재설정해주면 되어서 굿
• 자료 이동 불필요 굿

- 단점

• 구현 복잡 (동!적! 메모리 할당, 포인터 연산)
• 탐색 연산 비용이 높음(포인터를 이용해 처음부터 노드를 탐색해야 하기 때문), 이 부분은 배열이 훨씬 빠름
• 노드 개수가 n개면 탐색 연산의 시간 복잡도는
  • 배열 O(1)
  • 연결 리스트 O(n)

연결 리스트 종류

앞으로 배워나가야 할 리스트의 많은 종류가 여기, 연결 리스트의 한 부류이다.

• 단순 연결 리스트(Singly Linked List)
  • 단방향 링크 --> 체인 형식
  • 이전 노드에 접근하려면 처음부터 다시 시작해야 함(비효율)
• 원형 연결 리스트(Circular Linked List)
  • 단방향 링크
  • 마지막 노드는 첫 노드를 참조함
  • 이전 노드에 접근하려면 한 바퀴 돌아야 함(비효율)
• 이중 연결 리스트(Double Linked List)
  • 양방향 링크
  • 포인터가 두 개임(이전 것 참조, 다음 것 참조)
  • 이전 노드 접근이 가장 빠름(효율)

---

 

 

다음 시간엔 단순 연결 리스트의 실제 코딩 방법과 구체적인 적용 방법에 대해서 알아보도록 하자. 오늘은 개념!! 개념도 어렵다.