연결리스트

1. 각 원소에 저장되어 있는 다음 원소의 주소에 의해 순서가 연결되는 방식

2. 포인터로 자료를 순차적으로 연결함

3. 자료의 논리적인 순서와 물리적인 순서가 일치하지 않는 자료구조

 

연결 리스트 장점

1. 크기가 고정되지 않으며 기억 장소를 할당할 수 있는 한 계속 자료 삽입 가능

2. 중간에 데이터를 삽입하거나 삭제하는 연산이 용이함

3. 데이터 저장을 위한 기억 공간이 필요할 때마다 동적으로 만들어 쉽게 추가 가능

 

연결 리스트 단점

1. 구현이 복잡하고 어려움

2. 탐색 연산 비용 높음

 

단순 연결 리스트

1. 리스트의 각 노드에 다른 노드를 가리키는 포인터가 하나씩만 있는 것

2. 리스트를 구성하는 노드들이 한쪽 방향으로 연결된 구조

 

비사용 기억 공간

1. 연결 리스트를 사용하여 이미 생성된 노드들이 사용되지 않고 반환되는 경우 노드들을 포인터로 연결하여 리스트 구조를 유지하여 사용

2. 새로운 노드가 필요하면 이 리스트에서 할당

 

단순 연결 리스트의 역순 

연결 리스트 L = (a₁,a₂,...,a_n)이 있을 때 이 연결 리스트의 역순은 L = (a_n,a_n-1,...,a₁)이 됨.

 

단순 연결 리스트의 연결

1. 두 개의 단순 연결 리스트는 하나로 연결할 수 있음

2. 리스트 L1 = (a₁, a₂,...,a_n)이고 리스트 L2 = (b₁,b₂,...,b_m)인 경우 리스트 L1과 L2를 연결 하면 L = (a₁,a₂,...,a_n,b1,b₂,...,b_m)이 됨

 

이중 연결 리스트

1. 하나의 노드가 선행 노드와 후속 노드에 대한 두 개의 링크를 가지는 리스트

2. 링크가 양방향이므로 양방향으로 검색이 가능

3. 링크 필드가 두 개이므로 공간을 많이 차지하고 코드가 복잡함

 

일반 리스트

n >=0개 원소의 유한 수열 즉, a₀,a₁,a₂,...,a_n-1이고 여기서 a_i는 원자값이거나 또는 리스트임. 원자가 아닌 원소 a_i는 서브 리스트라고 함

 

아래첨자 https://corytips.tistory.com/65