단방향 연결 리스트 (Singly Linked List)

단방향 연결 리스트, 단방향 원형 연결 리스트

단방향 연결 리스트(Singly Linked List)

https://www.geeksforgeeks.org/what-is-linked-list/

두 번째 노드에서 첫 번째 노드로 이동할 수 없듯, 다음 노드는 이전 노드로 이동할 수 없다. 이는 단일 연결 리스트에는 다음 노드의 물리적 위치만 저장되어 있기 때문이다. 단일 연결 리스트의 마지막 노드의 참조는 항상 null 또는 nullptr을 가리킨다. 이 노드를 꼬리(tail)노드라고 한다.

특징

• 삽입 : 목록의 시작, 끝, 임의의 위치에 삽입이 가능하다.

• 삭제 : 시작, 끝, 임의의 위치에서 가능하다.

• 인덱스를 통해서 요소에 접근하는 것은 허용하지 않는다. 특정 노드에 도달하려면 순회가 필요하다.

• 배열에 비해 포인터를 저장하기 위해 추가적인 메모리가 필요하다.

---

단방향 원형 연결 리스트(Circular Singly Linked List)

https://www.geeksforgeeks.org/circular-linked-list/ Circular Singly LinkedList

단방향 원형 연결 리스트는 단일 연결 리스트와 같다. 단지 다른것은 마지막 노드는 항상 첫 번째 노드를 참조한다는 것이다.

요소를 삽입하는 4가지 방법

1. 빈 목록에 삽입 : O(1)

2. HEAD 다음(시작) 부분에 삽입 : O(1)

3. 목록 끝에 삽입 : O(1)

4. 노드 사이에 삽입 : O(N)