선형 리스트의 일반 구현과 응용

 1  선형리스트의 데이터 추가

이번엔 고정되지 않고 사용자가 입력하는 데이터가 가변적으로 작동하는 범용적인 코드를 작성한다.

먼저 배열에 빈칸을 추가한 뒤 데이터를 넣는다. 동일한 과정을 반복하면 배열이 생성된다.

이런 방식을 이용하여 선형 리스트 끝에 데이터를 추가하는 함수를 작성한다.

## 선형 리스트 생성 함수 구현 ##
katok = [] # 빈 배열

def add_data(friend) :
    katok.append(None)
    KLen = len(katok)
    katok[KLen-1] = friend
    
add_data('다현')
add_data('정현')
add_data('쯔위')
add_data('사나')
add_data('지효')

print(katok)

함수의 원리를 간단히 설명하면 매개변수로 저장할 데이터를 전달 받아 배열 맨 뒤에 빈칸을 추가한다.

배열의 현재 크기를 구하여 배열의 맨 끝 위치를 가리키는 [배열크기-1] 로  배열 맨뒤에 매개변수를 대입한다.

 

 2  데이터 삽입

이번엔 선형 리스트에서 데이터를 삽입하는 방식을 구현한다.

저번에 공부했던 리스트의 지정 위치에 데이터를 삽입하는 방식을 이용하여 코드를 구현한다.

## 데이터를 삽입하는 함수 ##
katok = ['다현', '정현', '쯔위', '사나', '지효']

def insert_data(position, friend) :
    if position < 0 or position > len(katok) :
        print("데이터를 삽입할 법위를 벗어났습니다")
        return
    
    katok.append(None) #빈칸 추가
    KLen = len(katok) #배열의 현재 크기
    
    for i in range(KLen-1,position, -1) :
        katok[i] = katok[i-1]
        katok[i-1]=None
        
    katok[position] = friend #지정한 위치에 친구 추가
    
insert_data(2, '솔라')
print(katok)
insert_data(6, '문별')
print(katok)

함수의 원리를 간단히 설명하면 매개변수로 삽입할 위치와 데이터를 넘겨받는다. 삽입할 위치가 배열 범위 안에 있다면 빈칸을 하나 추가하고 현재 배열의 길이를 계산해 마지막 위치(KLen-1)부터 삽입할 위치(position)까지 1씩 감소시키며 반복한다. 맨 뒤부터 한 칸씩 오른쪽으로 이동시키고, 빈칸을 만든다. 빈칸에 데이터를 삽입한다.

 

 3  데이터 삭제

이번엔 선형 리스트에서 데이터를 삭제하는 방식을 구현한다.

저번에 공부했던 리스트의 지정 위치에 데이터를 삭제하는 방식을 이용하여 코드를 구현한다.

## 데이터를 삭제하는 함수 ##
katok = ['다현', '정현', '쯔위', '사나', '지효']

def delete_data(position) :
    if position < 0 or position > len(katok) :
        print("데이터를 삽입할 법위를 벗어났습니다")
        return
    
    KLen = len(katok) #배열의 현재 크기
    katok[position] = None # 데이터 삭제
    
    for i in range(position + 1,KLen) :
        katok[i-1] = katok[i]
        katok[i]=None
        
    del(katok[KLen-1]) # 배열의 맨 마지막 위치 삭제
    
delete_data(1)
print(katok)
delete_data(3)
print(katok)

함수의 원리를 간단히 설명하면 매개변수로 삭제할 위치를 넘겨받는다. 삭제할 위치가 배열 범위 안에 있다면 배열의 길이(KLen)를 계산하고 삭제할 위치(position)의 데이터를 삭제한다. 삭제한 다음 위치부터 배열 길이 -1까지 1씩 증가시키면서 반복하면서 한 칸씩 왼쪽으로 이동시킨다. 이렇게 배열 끝까지 반복해 빈 자리를 이동시키고 맨 뒤의 빈칸을 삭제한다.

 

 4  기본 선형리스트의 완성

앞서 작성한 함수를 통합해서 완전한 선형 리스트를 처리하는 프로그램을 완성한다.

## 함수 선언 부분 ##
def add_data(friend) :
    
    katok.append(None)
    KLen = len(katok)
    katok[KLen-1] = friend
    
def insert_data(position, friend) :
    
    if position < 0 or position > len(katok) :
        print("데이터를 삽입할 법위를 벗어났습니다")
        return
    
    katok.append(None) #빈칸 추가
    KLen = len(katok) #배열의 현재 크기
    
    for i in range(KLen-1,position, -1) :
        
        katok[i] = katok[i-1]
        katok[i-1]=None
        
    katok[position] = friend #지정한 위치에 친구 추가
    
def delete_data(position) :
    if position < 0 or position > len(katok) :
        print("데이터를 삽입할 법위를 벗어났습니다")
        return
    
    KLen = len(katok) #배열의 현재 크기
    katok[position] = None
    
    for i in range(position + 1,KLen) :
        katok[i-1] = katok[i]
        katok[i]=None
        
    del(katok[KLen-1])
    
    
## 전역 변수 선언 부분 ##
katok = []
select = -1 # 1: 추가, 2: 삽입, 3: 삭제, 4: 종료

## 메인 코드 부분 ##
if __name__ == "__main__" :
    
    while(select != 4) : 
        
        select = int(input("선택하세요(1추가 2삽입 3삭제 4종료)-->"))
        if(select == 1) :
            data = input("추가할 데이터--> ")
            add_data(data)
            print(katok)
        elif(select == 2) :
            pos = int(input("삽입할 위치__>"))
            data = input("추가할 데이터--> ")
            insert_data(pos, data)
            print(katok)
        elif(select == 3) :
            pos = int(input("삭제할 위치__>"))
            delete_data(pos)
            print(katok)
        elif(select == 4) :
            print(katok)
            exit
        else :
            print("1~4 중 하나를 입력하세요. ")
            continue

 

 5  선형리스트의 응용

선형 리스트의 많은 응용 방법 중 가장 많이 쓰이는 것은 다항식(polynomial)을 저장하고 활용하는 것이다.

없는 항을 계수가 0이라고 가정하고 마지막 상수항은 x⁰ 이므로 1을 곱한 것과 같다고 가정한다.

그렇게 각 배열에 최고차항부터 나열한다고 가정한 후 다항식 계수들을 배열에 저장시키는 방식을 사용한다.

## 디힝식 선형 리스트 표현과 계산 프로그램 ##
## 함수 선언 부분 ##
def printPoly(p_x) :
    term = len(p_x) - 1
    polyStr = "P(x) = "
    
    for i in range (len(px)) :
        coef = p_x[i] #계수
        
        if(coef >= 0) :
            polyStr += "+"
        polyStr += str(coef) + "x^" + str(term) + " "
        term -= 1
        
    return polyStr

def calcPoly(xVal, p_x) :
    retValue = 0
    term = len(p_x) - 1
    
    for i in range (len(px)) :
        coef = p_x[i]
        retValue += coef * xVal ** term
        term -= 1
        
    return retValue

## 전역 변수 선언 부분 ##
px = [7, -4, 0, 5]

## 메인 코드 부분 ##
if __name__ == "__main__" :
    
    pStr = printPoly(px)
    print(pStr)
    
    xValue = int(input("X 값-->"))
    
    pxValue = calcPoly(xValue, px)
    print(pxValue)

 

앞서 다항식은 별 문제없이 처리되었다. 하지만 지수가 상당히 큰 다항식은 몇 백개의 배열을 선언해야 할 수 있다.

현실적으로 그런 건 처리하기 어렵다. 이를 간단히 처리하고자 모든 계수를 저장하지 않고 0이 아닌 계수와 항의 차수만 저장하는 방식을 사용할 수 있다.

## 특수 다항식 선형 리스트 표현과 계산프로그램 ##
## 함수 선언 부분 ##
def printPoly(t_x, p_x) :
    polyStr = "P(x) = "
    
    for i in range (len(px)) :
        term = t_x[i]
        coef = p_x[i]
        
        if(coef >= 0) :
            polyStr += "+"
        polyStr += str(coef) + "x^" + str(term) + " "
        term -= 1
        
    return polyStr

def calcPoly(xVal, t_x, p_x) :
    retValue = 0
    
    for i in range (len(px)) :
        term = t_x[i]
        coef = p_x[i]
        retValue += coef * xValue ** term
        term -= 1
        
    return retValue

tx = [300, 20, 0]
px = [7, -4, 5]

if __name__ == "__main__" :
    
    pStr = printPoly(tx, px)
    print(pStr)
    
    xValue = int(input("X 값-->"))
    
    pxValue = calcPoly(xValue, tx, px)
    print(pxValue)

tx배열은 차수를 저장하고 px배열은 해당 항의 계수를 저장해서 처리한다.