알고리즘 링크드 리스트(linked list)

알고리즘 링크드 리스트

-연결 리스트는 데이터와 포인트로 구성된 노드 간의 link을 이용해서 리스트를 구현한 자료구조입니다.

연결 리스트는 배열의 고정크기의 단점을 보완하기 위해 만들어졌으며 배열과 달리 연속적인 메모리 공간에

저장 되어 있지 않기 때문에 연결이 필요합니다.

 

그림을 설명 한다면.....

- Head 는 리스트의 처음을 나타냅니다.

- 노드는 데이터와 다음 노드를 가리키는 Next 포인터로 구성돼 있습니다.

- 각 노드는 next 포인터를 사용하여 다음 노드와 연결됩니다.

- 마지막 노드는 null을 가리켜 리스트의 끝을 나타 냅니다.

 

시간 복잡도

 

시작 위치에 대한 삽입/삭제 =   O(1)

1.0 마지막 위치에 대한 삽입/삭제 = O(1)-(마지막 요소 위치를 아는경우)

1.1 마지막 위치에 대한 삽입/삭제 = O(n)-(마지막 요소 위치를 모르는 경우)

중간 위치에 대한 삽입/삭제 = search time + O(1)

인덱싱   = O(n)

공간 낭비 = O(n)

 

특징

- 노드의 next부분에 다음 노드의 위치를 저장함으로써 선형적 데이터 자료구조를 가집니다.

- 연결되어있는 구조이기 때문에 특정 위치의 데이터를 탐색하기 위해서는 첫 노드부터 탐색을 시작하여 순차 접근만 가능합니다.

- 주소만 연결하면 되기 때문에 삽입 삭제가 배열에 비해 빠르고 쉽습니다.

- 불연속적 단위로 저장되기 때문에 조회에 불리하며 포인터로 인해 추가 저장공간이 필요합니다.

 

 

장점

1.크기가 가변적임

- 메모리가 허용하는 만큼 커질 수 있음

2. 삽입 삭제가 쉬움

-삽입 삭제시에 데이터 이동이 필요 없음

단점

1.래덤액세스가 불가능함 요소에 접근하려면 첫 번째 노드부터 순차적으로 접근해야함.

2.포인터를 위한 추가 메모리 공간이 필요함.