● 연결 리스트 (Linked List)
- 각 데이터에 저장되어 있는 다음 데이터의 주소에 의해 연결되는 방식
- 데이터의 물리적인 순서와 상관없이 포인터를 사용하여 논리적인 순서대로 연결하는 구조다.
- 데이터의 논리적인 순서와 물리적인 순서가 일치하지 않아도 된다.
● 장점
- 물리적인 순서를 맞추기 위한 오버헤드가 발생하지 않는다.
- 크기 변경이 유연하고, 더 효율적으로 메모리를 사용할 수 있다.
- 삽입 & 삭제가 용이하다.
● 단점
- 임의의 데이터에 접근할 때 시간이 오래 걸린다. <- 순차 접근만 가능하다.
- 포인터를 통해 다음 노드를 참조하므로 추가적인 메모리 공간이 발생한다.
● 단순 연결 리스트 (Simple Linked List)
- 노드가 하나의 링크 필드에 의해서 다음 노드와 연결되는 구조
- 단방향 순환하는 구조
- 뒤쪽 노드를 찾기 쉬운 반면 앞쪽 노드를 찾기 어렵다는 단점이 있다.
○ 삽입
① 공백 노드를 생성한다. 포인터 변수가 가리키게 하고, 새 노드의 데이터 필드에 값을 저장한다.
② 새 노드의 링크값을 저장한다. <- 새 노드의 링크 필드에 다음 노드의 주소 값을 저장한다.
③ 앞 노드와 새 노드를 연결한다. <- 앞 노드의 링크 필드에 새 노드의 주소 값을 저장한다.
○ 삭제
① 삭제할 노드의 앞 노드를 찾는다.
② 삭제할 노드의 앞 노드와 삭제한 노드의 다음 노드를 연결한다. <- 앞 노드에 삭제할 노드의 링크 필드값을 저장한다.
● 원형 연결 리스트 (Circular Linked List)
- 단순 연결 리스트의 마지막 노드의 링크 필드에 첫 번째 노드의 주소를 저장하여 원형으로 만든 구조
- 단방향 순환하는 구조
- 링크를 따라 계속 순회하면 이전 노드에 접근이 가능하다.
○ 삽입
① 공백 노드를 생성한다. 포인터 변수가 가리키게 하고, 새 노드의 데이터 필드에 값을 저장한다.
② 새 노드의 링크값을 저장한다. <- 새 노드의 링크 필드에 다음 노드의 주소 값을 저장한다.
③ 앞 노드와 새 노드를 연결한다. <- 앞 노드의 링크 필드에 새 노드의 주소 값을 저장한다.
○ 삭제
① 삭제할 노드의 앞 노드를 찾는다.
② 삭제할 노드의 앞 노드와 삭제한 노드의 다음 노드를 연결한다. <- 앞 노드에 삭제할 노드의 링크 필드값을 저장한다.
● 이중 연결 리스트 (Doubly Linked List)
- 노드가 링크 필드 두 개에 의해서 이전 노드와 다음 노드와 연결되는 구조
- 양방향 순환하는 구조
○ 삽입
① 공백 노드를 생성한다. 포인터 변수가 가리키게 하고, 새 노드의 데이터 필드에 값을 저장한다.
② 새 노드의 링크값을 저장한다.
-> 새 노드의 왼쪽 링크 필드에 앞 노드의 주소 값, 오른쪽 링크 필드에 다음 노드의 주소 값을 저장한다.
③ 앞 노드와 새 노드, 새 노드와 다음 노드를 연결한다.
-> 앞 노드의 오른쪽 링크 필드에 새 노드의 주소 값, 다음 노드의 왼쪽 링크 필드에 새 노드의 주소 값을 저장한다.
○ 삭제
① 삭제할 노드를 찾는다.
② 삭제할 노드의 앞 노드와 삭제한 노드의 다음 노드를 연결한다.
-> 앞 노드의 오른쪽 링크 필드에 삭제할 노드의 오른쪽 링크 필드값을 저장한다.
-> 다음 노드의 왼쪽 링크 필드에 삭제할 노드의 왼쪽 링크 필드값을 저장한다.
● 원형 이중 연결 리스트 (Circular Doubly Linked List)
- 원형 연결 리스트와 이중 연결 리스트를 결합하였다.
- 노드가 링크 필드 두개에 의해서 이전 노드와 다음 노드와 연결되고,
- 마지막 노드의 링크 필드에 첫 번째 노드의 주소를 저장하여 원형으로 만든 구조
- 양방향 순환하는 구조
○ 삽입
① 공백 노드를 생성한다. 포인터 변수가 가리키게 하고, 새 노드의 데이터 필드에 값을 저장한다.
② 새 노드의 링크값을 저장한다.
-> 새 노드의 왼쪽 링크 필드에 앞 노드의 주소 값, 오른쪽 링크 필드에 다음 노드의 주소 값을 저장한다.
③ 앞 노드와 새 노드, 새 노드와 다음 노드를 연결한다.
-> 앞 노드의 오른쪽 링크 필드에 새 노드의 주소 값, 다음 노드의 왼쪽 링크 필드에 새 노드의 주소 값을 저장한다.
○ 삭제
① 삭제할 노드를 찾는다.
② 삭제할 노드의 앞 노드와 삭제한 노드의 다음 노드를 연결한다.
-> 앞 노드의 오른쪽 링크 필드에 삭제할 노드의 오른쪽 링크 필드값을 저장한다.
-> 다음 노드의 왼쪽 링크 필드에 삭제할 노드의 왼쪽 링크 필드값을 저장한다.
'Study > Data Structure' 카테고리의 다른 글
| [자료구조] 1. 트리(Tree) - 이진 트리(Binary Tree), 트리 순회(Tree Traverse) (0) | 2021.07.01 |
|---|---|
| [자료구조] 큐(Queue) - 선형 큐(Linear Queue), 원형 큐(Circular Queue), 연결 큐(Linked List Queue), 데크(Double-Ended Queue) (0) | 2021.06.29 |
| [자료구조] 스택(Stack) (0) | 2021.06.29 |
| [자료구조] 선형 리스트 (Linear List) (0) | 2021.06.28 |
| [자료구조] 자료구조(Data Structure)란? (0) | 2021.06.28 |
댓글