List

Contents

• 리스트 이론
  • 리스트 분류
  • 리스트 종류
  • 문제풀이 tip
• 자료 구조 비교
• 면접 문제

1. 리스트 이론

1) 리스트 분류

유형\구현	순차 자료구조	연결 자료구조	비순차 자료구조
스택	순차 스택	연결 스택
큐	순차 큐	연결 큐
데큐	순차 데큐	연결 데큐
트리	순차 트리	연결 트리
그래프	순차 그래프	연결 그래프
장점	논리순서=물리순서: 접근(access) 속도 빠름	논리!=물리 순서(주소 연결): 물리 순서를 맞추기 위한 오버헤드가 없음
단점	삽입/삭제 비효율. 메모리 비효율

2) 종류

: TO DO!! -> 구현

• 단순 연결 리스트
• 이중 연결 리스트
• 원형 리스트

3) 문제 풀이 tip

• Runner(부가 포인터): 2개의 포인터를 동시에 사용하여 리스트를 순회하는 것. C++에서는 begin(), end()로 부가 포인터를 사용 중이다.일반적으로, 2개의 리스트를 정렬하며 합칠 때 사용한다.

2. 자료구조 비교

	Array	Vector(Array List)	(Double Linked) List	Forward List
장점	임의 접근: O(1)	가변 크기. 빠른 접근: O(1) (순차 추가/삭제는 list보다 빠름)	빠른 삽입/삭제: O(1). 요소 양방향 접근.	DL list와 비교하여, 메모리 사용이 적다. 삽입/삭제가 가장 빠르다.
단점	고정 크기	삽입/삭제 비효율: O(N) (N개의 메모리를 추가 할당)	임의 접근 불가: O(N)	임의 접근 불가. 양방향 접근 불가

3. 면접 문제

 How do you find the middle element of a singly linked list in one pass?

 How do you check if a given linked list contains a cycle? How do you find the starting node of the cycle?

 How do you reverse a linked list?

 How do you reverse a singly linked list without recursion?

 How are duplicate nodes removed in an unsorted linked list?

 How do you find the length of a singly linked list?

 How do you find the third node from the end in a singly linked list?

 How do you find the sum of two linked lists using Stack?

 단일 연결 리스트에서 맨 뒤에서 m번째 원소를 반환하는 함수를 구현하여라.
m = 0이면, 맨 마지막 원소를 반환 {1,2,3,4,5,6}, m = 2 (리턴값 4)