10. 선형리스트(5-2)

1. 선형리스트(linear list)의 개념 

 기억장소에 각 원소들이 연속적으로 나타나며, 리스트 시작으로부터  

     상대적으로 위치를 계산할 수 있으므로 임의의 노드에 접근 가능 한 구조 

 리스트 구성의 예

 선형리스트에서의 노드의 삽입 

 리스트에 노드 25를 삽입 

 n개의 원소로 구성된 선형 리스트에서 임의의 원소를 삽입하기 위한 평균 이동 횟수 

 선형리스트에서의 노드의 삭제 

2. 선형리스트(linear list)의 연산 

 리스트에서 처리 할 수 있는 연산 

 길이(length) : 리스트의 길이 

 접근(access) : 리스트의 내용을 조사하거나 변경하기 위해 위치를 찾는다. 

 검색(search) : 리스트의 노드들 중에서 필요한 노드( i번째 원소)를 찾는다.(1 ≤i ≤ n) 

 저장(store) : i번째에 새로운 원소를 저장한다.(1 ≤ i ≤ n) 

 삽입(insert) : 리스트에 새로운 노드의 첨가(i번째 새로운 원소를 삽입한다.  (1 ≤ i ≤ n)) 

i, i+1, ..., n의 인덱스 값을 가지고 있던 원소들을 i+1, i+2, ..., n+1의 인덱스 값을 갖는다. 

           삭제(delete) : 리스트에서 노드의 제거( i번째 원소를 삭제한다.( 1 ≤ i ≤ n)) 

i+1, i+2, ..., n의 인덱스 값을 가지고 있던 원소들을 i, i+1, ..., n-1의 인덱스 값을 갖는다. 

 복사(copy) : 리스트의 전체 혹은 일부를 복사하여 새로운 노드를 만든다.  

 정렬(sort) : 어떤 기준으로 리스트를 정렬(오름차순, 내림차순)시킨다.  

 병합(merge) : 둘 또는 그 이상의 리스트를 하나의 리스트로 만든다. 

 분리(split) : 한 리스트를 둘 또는 그 이상의 리스트들로 나눈다.