21/06/24 목
리스트가 헷갈리는것이 너무 많아 짖는개,,,씨꺼를 많이 참고 했다 다시 정리해보자
배열과 연결리스트
일단 메모리상의 배치는 배열의 경우 연속, 연결리스트의 경우 불연속이다. 배열을 생각해보면 데이터만 딱딱 저장하면 될 뿐 딱히 추가적으로 필요한 공간이 없다. 하지만 연결리스트에서는 각 원소가 다음 원소, 혹은 이전과 다음 원소의 주소값을 가지고 있어야 한다.
그래서 N에 비례하는 만큼의 메모리를 추가로 쓰게 된다.
연결리스트 연산
임의의 위치에 있는 원소를 확인/변경하는 연산
배열과는 다르게 임의의 위치에 있는 노드로 가기 위해서는 그 위치에 도달할 때까지 첫번째 부터 순차적으로 방문을 해야한다.
모든 원소들은 메모리 어딘가에 있겠지만 우리는 첫번째 노드의 주소만 알고 있기 때문에 우리가 4번째있는 노드의 값을 확인하고 싶어도 첫번째 노드의 주소만 알고 있기 때문에 첫번째 노드로 가서 두번째로 넘어가고, 세번째로 가고 네번째로 넘어가야한는 루트를 가진다.
그렇기 때문에 k번째 원소를 보기위해서는 O(k)의 시간이 필요하고 O(N)의 시간 복잡도를 가진다.
11 List - polynomials
list형태로 polynomials 구현하는 방법
각 항별로 노드를 만든다.
계수와 지수, 그 다음 항을 가리키는 포인터 -> 세개의 구성 요소를 갖는 data structure 선언
typedef struct polyNode* polyPointer;
typedef struct polyNode {
int coef;
int expon;
polyPointer link;
};
polyPointer a,b;
