연결 리스트(Linked List)

▷ 연결 리스트(Linked List)

1. 단방향 연결 리스트.

- 한쪽 방향으로 연결된 리스트이다.

- 자료 생성시 노드가 생성되고 포인터는 생성된 포인터를 가르킨다.

2. 양방향 연결 리스트

- 양쪽 방향으로 연결된 리스트이다.

- 자료 생성시 노드가 생성되고 포인터는 생성된 포인터를 가르킨다.

그리고 새로 생성된 노드의 포인터는 전 노드를 가르킨다.

3. 환형 연결 리스트

- 양방향 연결 리스트와 비슷하지만 마지막 노드의 포인터가 가리키는 노드는 리스트의 처음 노드이다.

장점: 늘어선 노드의 중간지점 자료의 추가와 삭제가 O(1)의 시간내에 가능하다.

단점: 특정 위치의 데이터를 검색하는데에 O(n)의 시간이 걸린다는 단점이 있다.