다항식이란 ax의 e승 형식의 합으로 구성된 식이다. 각 항에는 계수, 변수, 지수가 있는데, ax의 e승에서 a는 계수, x는 변수, e는 지수이다. 다항식은 지수가 높은 항부터 낮은 항 순서로 항을 나열하며, 가장 큰 지수가 그 다항식의 차수가 된다. 다항식 A(x)= 2x의 3승 + 3x의 2승 + 4x + 5는 항이 네 개로 구성된 다항식이며 차수는 3이 된다. 결국 다항식은 항을 나열한 것이므로 선형 리스트를 사용하여 표현할 수 있고 연산을 처리할 수 있다.

다항식의 데이터와 연산의 특징을 추상화하여 추상 자료형으로 정리하면 [ADT 3-1]과 같다.

추상 자료형 정의에 따라 A(x)= 4x의 3승 + 3x의 2승 + 2 는 p1 = ( ( 3, 4), (2, 3), (0, 2) ) 와 같이 각 항을 지수와 계수의 쌍으로 묶어 세 개의 항을 p1 선형 리스트의 원소로 정의할 수 있다. 다항식에서는 첫 번째 항이 최고차항이므로 첫 번째 항의 지수를 알면 가능한 최다항 개수까지 알 수 있다. 예를 들어, 첫 번째 항의 지수가 3이면 그 다항식은 3차 다항식이 된다. 이 다항식에 포함될 수 있는 항은 x의 3승, x의 2승, x의 1승 x의 0승(상수항) 이므로 가능한 최다항 개수는 네 개이다. n차 다항식 P(x)는 다음과 같이 표현할 수 있다. 이때 an은 지수가 n인 항의 계수를 나타낸다.

지수가 n인 다항식은 최다항 개수가 ( n+1 ) 개 이므로 원소가 ( n + 1 )개인 배열을 사용하여 [그림 3-15]의 (a)와 같이 순차 자료구조로 표현할 수 있다. 배열의 인덱스는 다항식 항의 지수를 표현하고 배열 원소에는 다항식 항의 계수를 저장한다. 배열 P에서 인덱스 i는 지수가 (n-i)인 항에 대응되는 배열 원소를 의미하고 P[i]의 값은 지수가 (n-i)인 항의 계수가 된다. 예를 들어 (b)와 같다. 다항식 A(x)에서 x의 1승 항이 없다는 것은 0x의1승 항이라는 것이므로 A[2]의 값은 0이 된다.

다항식의 각 항의 계수를 정해진 인덱스의 배열 원소에 저장하여 사용하는 방법은 지수를 따로 저장하지 않기 때문에 표현하기 쉽고 간단하다. 그러나 차수와 항의 계수 차이가 심한 희소 다항식은 메모리가 낭비된다.

예를 들어 다항식 B(x) = 3x의 1000승 + x + 4는 지수는 1000이지만 항의 개수는 세 개 뿐인 희소 다항식이다. [그림 3-14]와 같은 순차 자료구조로 저장하려면 [그림 3-16]의 (a)와 같이 배열 크기가 1001인 배열을 사용해야 한다. 배열 원소 1001개 중 실제로 사용하는 것은 세 개 뿐이고, 나머지 배열 원소 공간인 998개가 낭비된다. 이러한 희소 다항식은 지수에 따라 (지수 + 1) 크기의 배열을 생성하는 것보다 항의 개수에 따라 배열 크기를 결정하는 것이 메모리 사용 면에서 효율적이다. 이 경우에는 인덱스를 이용해 지수를 표현할 수 없으므로 (b) 와 같이 <지수, 계수> 쌍을 2차원 배열로 저장한다. 2차원 배열에서 행의 개수는 희소 다항식 항의 개수가 된다. 0번 열은 항의 지수를 저장하고, 1번 열은 계수를 저장한다.

[ADT 3 - 1]에 정의된 다항식 연산 중에서 덧셈 연산을 살펴보자. A(x) +B(x) = C(x)는 지수가 같은 항이 있으면 계수를 더하여 결과 다항식 C(x)의 항을 만들고, 같은 지수의 항이 없으면 그 항은 그대로 C(x)의 항이 된다.