[Java로 배우는 자료구조] 제4-1장: 연결리스트의 개념과 기본연산

<List>

• 리스트(list): 기본적인 연산은 insert(삽입), remove(삭제), search(검색) 등. 리스트를 구현하는 대표적인 두 가지 방법은 배열, 연결리스트이다.
• 배열의 단점: 크기가 고정되어 있어 reallocation 필요. 리스트의 중간에 원소를 삽입하거나 삭제할 경우 다수의 데이터를 옮겨야 함.
• 연결리스트: 다른 데이터의 이동 없이 중간에 삽입, 삭제가 가능하며 길이의 제한이 없음. but, 랜덤 액세스 불가능.

 

<노드>

• 연결리스트를 구성하는 기본 단위
• 각각의 노드는 "데이터 필드"와 하나 혹은 그 이상의 "링크 필드"로 구성
• 링크 필드는 다음 노드를 참조
• 첫 번째 노드의 주소는 따로 저장해야 함.
• 연결 리스트를 다루는 프로그램에서 가장 주의할 점은 내가 작성한 코드가 일반적인 경우만이 아니라 특수한, 혹은 극단적인 경우에도 문제 없이 작동하는지 철저히 확인하는 것이다. 이 경우에는 기존의 연결 리스트의 크기가 0인 경우, 즉 head가 null인 경우에도 문제가 없는지 확인해야 한다.
• 단순연결리스트에 새로운 노드를 삽입할 때 삽입할 위치의 바로 앞 노드의 주소가 필요하다. 즉 어떤 노드의 뒤에 삽입하는 것은 간단하지만, 반대로 어떤 노드 앞에 삽입하는 것은 간단하지 않다.
• 단순연결리스트에 어떤 노드를 삭제할 때는 삭제할 노드의 바로 앞 노드의 주소가 필요하다. 삭세할 노드의 주소만으로는 삭제할 수 없다.
• 연결리스트의 노드들을 처음부터 순서대로 방문하는 것을 순회(traverse)한다고 말한다.

너무 이해 안가서 복습각ㅎ