List

1. List

- 순서를 가진 데이터의 집합을 가리키는 추상자료형

동일한 데이터를 가지고 있어도 상관없음

구현방법에 따라 두 가지로 나뉨

순차 List : 배열을 기반으로 구현된 List

연결 List : 메모리의 동적할당을 기반으로 구현된 List

 

List 사용을 위한 주요 함수

함수명	기능
addtoFirst()	List의 앞쪽에 원소를 추가하는 연산
addtoLast()	List의 뒤쪽에 원소를 추가하는 연산
add()	List의 특정 위치에 원소를 추가하는 연산
delete()	List의 특정 위치에 있는 원소를 삭제하는 연산
get()	List의 특정 위치에 있는 원소를 리턴하는 연산

 노드 

연결 리스트에서 하나의 원소에 필요한 데이터를 갖고 있는 자료단위

#데이터 필드 

- 원소의 값을 저장하는 자료구조

- 저장할 원소의 종류나 크기에 따라 구조를 정의하여 사용함

#링크 필드

- 다음 노드의 주소를 저장하는 자료구조

 

헤드

List의 처음 노드를 가리키는 자료구조

 

단순 연결 리스트의 삽입 연산

'A','C','D'를 원소로 갖고 있는 List의 두번째에 'B'노드를 삽입할때

1. 메모리를 할당하여 새로운 노드 new 생성

2. 새로운 노드의 new의데이터 필드에 'B'저장

3. 삽입될 위치의 바로 앞에 위치한 노드의 링크 필드를 new에 복사 

4. new의 주소를 앞 노드의 링크필드에 저장

 

이중연결 리스트

- 양쪽 방향으로 순회할수 있도록 노드를 연결한 리스트

- 두개의 링크필드와 한개의 데이터 필드로 구성