리스트(LIST)와 링크드리스트(LINKED-LIST)
배열의 경우 미리 정해놓은 배열의 크기 이상의 데이터를 추가할 수 없다는 단점이 있다.
(데이터를 더 많이 추가하고자 한다면 배열을 새로 할당하고 기존의 데이터를 옮겨줘야 함)
그와 달리 리스트는 크기를 넘어서 데이터를 추가할 수 있다.
1. 리스트 (LIST <T>)
: 자료구조를 더 편하게 사용할 수 있게 제네릭으로 선언됐기 때문에 다양한 타입을 다룰 수 있고 *박싱과 *언박싱에서도 비교적 자유로운 모습을 보인다.
* 박싱 : 값 형식의 데이터를 참조 형식의 데이터로 변환하는 것
* 언박싱 : 참조 형식의 데이터를 값 형식으로 변환하는 것
박싱과 언박싱은 최적화의 관점에서 지양해야 함.
- 리스트는 기존의 크기를 넘어서 데이터를 추가할 수 있다.
- 단, 기존의 크기를 넘어설 경우 기존 크기의 2배를 메모리에 재할당하게 됨(ex. 12 -> 24)
(재할당을 반복하는 것이 바람직한 것은 아니기 때문에 처음부터 사용할 크기를 제대로 정하는 것이 옳은 방법)
1) 값을 삽입할 때
- 맨 뒤에 데이터 추가 시 O(1)의 시간 복잡도
- 맨 앞이나 중간에 추가시 O(n)의 시간 복잡도
- List.Add(데이터) : 맨 뒤에 데이터 추가
- List.Insert(n, 데이터) : n번째 위치에 데이터 추가
2) 값을 삭제할 때
- 맨 뒤의 데이터를 삭제할 시 O(1)의 시간 복잡도
- 맨 앞이나 중간의 값을 삭제할 시 O(n)의 시간 복잡도
- List.Remove(데이터) : 데이터를 삭제
- List.RemoveAt(n) : n번째 데이터를 삭제
3) 검색
- 리스트를 순회해야 하기 때문에 O(n)의 시간 복잡도
- List.Contains(데이터) : 리스트 내에 데이터가 존재하는지 확인
4) 읽기
- 연속된 메모리 공간에 위치하므로 인덱스로 접근 가능 O(1)의 시간 복잡도
- List[n] : n번째의 데이터 읽기
2. 링크드리스트 (LinkedList <T>)
: 링크드리스트는 메모리상에 데이터가 연속적으로 위치하지 않음.
하나의 원소가 다음 데이터의 메모리주소를 참조하기 때문에 데이터를 선형으로 다룰 수 있음
1) 리스트의 종류
- Node : 링크드리스트에서 하나의 데이터를 칭하는 말
- Node들이 어떻게 참조하고 있느냐에 따라 여러 종류로 나뉠 수 있음
(1) 단일연결리스트
: 노드들이 한쪽 방향으로만 연결되어 있는 리스트
(2) 원형연결리스트
: 마지막 노드가 첫 번째 노드를 가리키고 있는 리스트
(3) 이중연결리스트
: 노드들이 양쪽 방향으로 참조하고 있는 리스트
(4) 원형이중연결리스트
: 마지막노드와 첫번째 노드까지 모두가 양방향으로 참조하고 있는 리스트
2) 링크드리스트
- 이중 링크드리스트는 (3) 이중연결리스트
- 메모리 공간 내에서 서로 떨어져 있기 때문에 인덱스로는 접근이 불가
- 원소들을 순회하기 때문에 읽기, 검색은 O(n)의 시간복잡도
- 삽입과 삭제는 데이터를 새로 할당하고 참조만 바꾸면 되기 때문에 O(1)의 시간복잡도
(단, 노드를 특정하는 것이 아니라 데이터를 탐색해서 추가해야 한다면 O(n)의 시간복잡도)
(1) 삽입
- LinkedList.AddFirst(데이터) : 맨 앞의 노드에 데이터 추가
- LinkedList.AddLast(데이터) : 맨 뒤의 노드에 데이터 추가
[ LinkedListNode <T>: 위 명령어들의 반환형 ]
- LinkedList.AddAfter(node, 데이터) : LinkedListNode로 반환반은 노드의 위치 뒤에 데이터를 추가
- LinkedList.AddBefore(node, 데이터) : LinkedListNode로 반환받은 노드의 위치 앞에 데이터를 추가
(2) 삭제
- LinkedList.Remove(node) : LinkedListNode로 반환받은 노드를 삭제+ 매개변수로 직접 값을 삭제하는 것도 가능하지만 이럴 경우 시간복잡도 O(n)을 가짐 - LinkedList.RemoveFirst : 맨 앞의 노드 삭제 - LinkedList.RemoveLast : 맨 뒤의 노드 삭제
(3) 읽기, 검색
- 처음부터 원하는 값이 나올 때까지 순회해야 하므로 O(n)의 시간복잡도를 가짐
** 틀린 내용이 있다면 말씀 부탁드립니다 **