linkedlist

List는 구조가 단순하여 가장 널리 사용되는 기초적인 자료구조

순서대로 저장하는 자료구조 -> 여러 개의 자료가 일직선으로 서로 연결된  '선형 구조'

Ex) 리스트의 구조

문자열: 'Data'

D-a-t-a

문자열이 순서대로 저장되는 선형구조

리스트의 추상 자료형

리스트의 추상 자료형 입니다. 추상자료형에 제가 만들 list의 함수들과 역활등이 정해져 있습니다. 

리스트는 배열 리스트와 포인트를 이용하여 구현하는 연결리스트 두 가지로 나눌 수 있습니다.

배열 리스트는 미리 크기를 정해줘야 하지만

연결 리스트는 미리 크기를 정해줄 필요가 없습니다(새로운 원소를 추가할 경우 동적으로 원소를 생성하고 포인터로 이어주기만 하면 됩니다.)

연결 리스트

연결리스트의 노드는 자료를 저장하는 부분(data)와 링크를 저장하는 부분(link)로 구성됩니다.

연결리스트의 제일 마지막 노드는연결되는 다음 노드가 더 없으므로 NULL값으로 설정한다.

연결리스트의 노드 추가

연결리스트에 노드를 추가할 때 순서

1. 들어갈 위치를 찾는다.

2. 들어갈 위치의 이전 노드와 다음 노드를 정하고, 들어갈 새로운 노드를 생성한다.

3. 새로운 노드의 링크를 이전노드의 링크로 연결하고, 이전노드는 새로운 노드로 연결한다.

연결 리스트의 노드 제거

연결 리스트에 노드를 제거할 때 순서

1. 들어갈 위치를 찾는다.

2. 기존 노드를 삭제할 노드 다음 링크와 연결한다.

3, 삭제할 노드의 메모리를 해제한다.(해제해야 메모리 누수가 발생하지 않는다.)

연결 리스트의 장, 단점

장점

1. 추가 원소 이동 불필요

2. 최대 원소 개수 지정 불필요

단점

1. 구현의 어려움

2. 탐색 연산의 비용이 높음