연결 리스트 (Linked List)

연결리스트(Linked List)란?

동적으로 크기가 변할 수 있고 삭제나 삽입시에 데이터를 이동할 필요가 없는 자료구조가 연결리스트입니다.

- 데이터와 링크로 구성되어있고 링크가 데이터들을 연결하는 역할을 합니다.

- 요런 형태입니다.

연결리스트는 노드로 구성되어있는데,

- 노드 : 데이터 필드, 링크 필드로 구성

- 데이터 필드 : 실제 저장할 데이터가 있는 공간

- 링크 필드 : 다른 노드를 가리키는 포인터를 저장

배열의 경우 중간에 데이터를 삽입하려면 삽입하려는 위치에 있는 데이터와 그 이후에 있는 데이터들을 모두 한 칸씩 뒤로 움직여야하는데, 연결리스트는 그럴 필요가 없습니다.

- 삽입하려는 위치의 링크만 변경해 주면 됩니다.

단순 연결 리스트

- 위의 연결 리스트가 단순 연결 리스트

- 데이터 필드와 링크 필드를 갖는 노드들의 집합

- 마지막 링크 필드는 NULL

원형 연결 리스트

- 연결리스트의 가장 끝 노드가 첫번째 노드를 가리키는 리스트

- 큐에 사용되면 rear, front가 무제한으로 늘어나는 현상을 완화시킬 수 있음

이중 연결 리스트

- 단순 연결 리스트에서 뒤에 있는 노드는 찾기 쉽지만 앞에 있는 노드를 찾기 어려운 점을 해결한 리스트

- 링크 필드가 2개로, 선행 노드와 연결된 링크필드, 후행 노드와 연결된 링크필드의 두 가지로 구성되어있다.

- 링크가 양방향이기 때문에 양방향으로 검색이 가능하다. -> 코드가 더 복잡해짐

- 원형 연결 리스트처럼 마지막 링크 필드를 첫 번째 노드로 연결시키는 경우도 있음 (꼭 다 그렇지는 않음)

연결리스트의 장점

- 삽입, 삭제가 빠르다.

- 메모리 공간을 동적으로 설정할 수 있다.

- 크기의 제한이 없다.

연결리스트의 단점

- 배열에 비해 구현 방법이 복잡하다.

- 배열에 비해 구조가 복잡해 오류가 날 가능성이 높다.

- 링크 필드를 위한 추가 공간이 필요하다.