선형 자료구조 2 (리스트)

안녕하세요!

 

게임개발자가 되기위해 공부하고있는 구구입니다.

오늘은 List에 대해 알아보도록 하겠습니다.

 

---

• 리스트(List)

1. ArrayList - 내부적으로 배열을 사용
2. LinkedList - 링크 포인터를 사용
3. List<T> - 제네릭 타입

- 리스트를 다른말로 Dynamic Array라고 부름.

 

 

 

 

 

 

 

• ArrayList의 선언 방법

ArrayList list = new ArraList();

 

• ArrayList의 특징

- 데이터의 추가 삭제가 자유롭다.

- 데이터 타입에 관계없이 삽입 가능. (효율이 좋지 못함)

- 생성 시 크기를 지정하지 않음.

- 배열보다 속도는 느림.

- 배열은 Length를 이용해서 배열의 길이를 파악했다면 List는 Count를 이용해서 요소의 수를 확인함.

ex) list.Count(요소의 수)

 

• Boxing

- 값 형식을 참조형식으로 변환하는 것

 

• Unboxing

- 참조형식을 값형식으로 변환하는 것

 

---

• List<T>(Generic List) 의 선언방법

List<string> MusicList = new List<string>();

List<int>, List<string[]>

 

- 저장할 데이터 타입을 T에 인자값으로 넘김

- 실제 arrayList보다 제너릭 리스트를 사용하라고 권장을 많이 함.

 

• 활용 메소드

Add : 객체를 ArrayList 끝부분에 추가

Contains : 해당 데이터가 있는지 확인 후 bool값 반환

Insert : ArrayList에 저장된 인덱스에 데이터를 삽입( List.Insert(int index, object value); )

Remove : 지정된 값을 찾아서 삭제

RemoveAt : 지정된 인덱스 삭제(전체 길이가 줄어들음)

Sort : ArrayList에 포함된 데이터를 정렬 (데이터 타입이 동일할 경우) (거꾸로 출력하고 싶으면 for문으로 바꾸기.)

 

• 활용 프로퍼티

Count : ArrayList에 데이터의 총 개수

Capacity : ArrayList에 저장할 수 있는 저장공간의 수 설정

 

 

 

 

 

 

---

• Linked List

- ArrayList : 메모리에 할당받을때 연속적으로 공간을 차지함.(하나하나의 저장공간을 element라 부름)

- Linked List : 메모리에서 떨어져있지만 링크포인트로 인해 연결됨.(하나하나의 저장공간을 Node라 부름)

 

 

• Linked List 특징

- 추가 데이터에 대한 연산 불필요(추가와 제거가 쉬움)

- 구현이 어려움

- 탐색 연산의 비용이 높음

 

 

• Singly Linked List 구조

단순 연결 리스트(Singly Linked List)

 

 

 

• Singly Linked List 특징

- 이전노드는 없지만 다음 노드의 링크포인트를 가지고 있음

- 데이터 자체는 Doubly Linked List 보다 작음(이전 노트 링크 포인트가 없기 때문)

- SinglyLinkedList 로 호출

 

ex) SinglyLinkedList<int> list = new SinglyLinkedList<int>();

 

 

• Doubly Linked List(이중 연결 리스트)

• Doubly Linked List 특징

- 양방향 탐색이 가능

- 노드에 이전 노드와 다음 노드를 가리키는 포인터를 가지고 있음

- First(첫번째 노드 호출 가능)

- LinkedList로 호출

 

ex) LinkedList<int> number = new LinkedList<int>();

 

LinkedList<T>

1. AddFirst
2. AddLast
3. AddAfter
4. AddBefore

 

• Doubly Circular Linked List(원형 연결 리스트)

• Doubly Circular Linked List 특징

- 처음과 마지막 노드를 서로 연결

- 마지막 노드의 Next는 첫번째 노드를 가리키고 있음

- 첫번째 노드의 Previous는 마지막 노드를 가리키고 있음

 

 

---

마지막 정리

 

• ArrayList, List<T>

- 데이터 검색에 유리

- 데이터 추가/삭제가 느림

 

• LinkedList<T>

- 데이터 추가/삭제가 빠름

- 데이터 검색이 느림