[자료구조] 리스트의 개념, 리스트 사용을 위한 추상자료형

리스트(List)

: 자료를 순서대로 저장하는 자료구조

 

구조가 매우 단순

여러 개의 자료가 일직선으로 서로 연결된 선형 구조

선형구조 - 자료가 1:1 관계인것.

 

리스트의 구현

배열리스트(Array List)

C언어에서 제공하는 배열(array)을 이용하여 구현된 리스트

 

배열 vs. 배열리스트

배열 : 같은 자료형의 데이터가 메모리 상에 연속적으로 저장되는 것

배열리스트 : 자료가 일직선으로 서로 연결

 

배열리스트는 배열과 달리 서로 연결되어있어야 하기 때문에

중간에 자료를 제거하거나 추가할때 고려해야할 사항들이 있음

 

끊기지 않도록 자료를 서로 연결시켜주어야함

 

중간에 자료를 추가할 경우에는

두ㅣ의 자료들을 한칸씩 뒤로 이동시켜줘야함

 

연결리스트(Linked List)

- 포인터를 이용한 구현

 

---

리스트 사용 예

 

1. 문자리스트(문자열 String)

문자 하나하나가 연결되어 있는 것

 

2. 문자열 리스트

문자열이 저장되어 있는 것.

 

3. 행렬(Matrix)

4*4 행렬은 리스트안에 리스트가 구성되어있음

 

4. 다항식(Polynomial Equation)

계수와 차수를 배열 리스트로 나타내기도 한다

---

리스트 추상자료형

이름		입력(input)	출력(output)	설명
리스트 생성	createList()	최대 원소 개수 n	리스트	최대 n개의 원소를 가지는(배열의 크기) 공백 리스트 1을 생성
리스트 삭제	deleteList()	리스트1	N/A	리스트의 모든 원소 제거
원소 추가 가능 여부 판단	isFull()	리스트1	true/false	리스트의 원소 개수가 최대 원소개수와 같은지 반환. 배열 리스트인경우에만 사용. (연결리스트에서는 항상 false)
원소 추가	addElement()	리스트1 원소 위치 p 원소 e	성공/실패 여부	원소 e를 리스트의 특정위치 p 에 추가
원소 제거	removeElement()	리스트1 원소 위치 p	성공/실패 여부	리스트의 위치 p에 있는 원소를 제거
리스트초기화	clearList()	리스트1	N/A	리스트의 모든 원소를 제거
원소 개수	getListLength()	리스트1	원소의 개수	리스트의 원소 개수를 반환
원소 반환	getElement()	리스트1 원소 위치 p	원소(Element)	리스트의 위치 p에 있는 원소를 반환