8-1장 선형 리스트

1. 선형 리스트 정의하기 

 

선형 리스트 (linear list)

- 리스트 : 데이터를 순서대로 나열한 자료구조 

- 가장 단순한 구조를 가진 리스트 

 

- 노드(node)

 : 리스트의 각 요소 

 

- 각각의 노드는 데이터와 다음 노드를 가리키는 포인터를 가짐 

 

- 머리 노드(head node)

: 처음에 있는 노드 

 

- 꼬리 노드 (tail node)

: 끝에 있는 노드 

 

 

2. 배열로 선형 리스트 만들기 

 

1) 다음 노드 꺼내기 

 - 1만큼 큰 인덱스를 갖는 요소에 접근 

 

2) 노드의 삽입과 삭제 

 -삽입 요소의 다음 요소를 하나씩 뒤로 옮겨야 함

 - 삭제하는 경우에도 모든 요소를 뒤로 밀거나 앞으로 당겨야 함

 

 

- 배열로 구현한 선형리스트의 문제점

• 쌓이는 데이터의 크기를 미리 알아야함
• 데이터의 삽입, 삭제에 따라 데이터를 모두 옮겨야 하기 때문에 효율이 좋지 않음