[자료구조] 선형리스트(liner list)=순차 리스트(Sequential List)의 개념과 구현 by python

선형 리스트

 

선형리스트의 기본

 

선형 리스트의 개념

• 데이터를 일정한 순서로 나열한 자료구조이다.
• =순차 리스트(Ordered List)
• 입력 순서대로 저장하는 데이터에 적합하다.
• 구현하는 가장 기본적인 방법은 배열을 이용하는 것이다. (파이썬의 자료형에서는 List)
• 컴퓨터 메모리에서도 저장될 때 시작 위치부터 순차적으로, 빈자리 없이 저장된다.

 

선형리스트의 원리

 

데이터 삽입

• 새로운 원소를 삽입하려면, 삽입할 자리를 만들기 위해, 삽입할 위치 이후의 원소들을 모두 한 자리씩 뒤로 옮겨야한다.
• ① 원소를 삽입할 빈 자리 만들기 (삽입할 자리 이후의 원소들을 한 칸씩 뒤로 이동)
• ② 빈 자리에 원소 삽입하기

삽입할 자리를 만들기 위한 자리 이동 횟수

• N 개의 원소로 이루어진 선형 리스트에서 인덱스 K에 원소를 삽입하는 경우
• 마지막 원소의 인덱스 - 삽입할 자리의 인덱스 + 1 -> (N - 1) - K + 1

데이터 삭제

• 원소를 삭제하려면, 삭제한 이후에 빈자리를 채워주기 위해 , 삭제한 위치 이후의 원소들을 모두 한 자리씩 앞으로 옮겨야한다.
• ① 원소 삭제하기
• ② 삭제한 빈 자리 채우기 (삭제한 자리 이후의 원소들을 한 칸씩 앞으로 이동)

삭제후, 빈 자리를 채우기 위한 자리 이동 횟수

• N개의 원소로 이루어진 선형 리스트에서 인덱스 K의 원소를 삭제하는 경우
• 마지막 원소의 인덱스 - 삭제한 자리의 인덱스 -> (N - 1) - K

데이터 탐색

• 순차 리스트는 배열로 구현하므로 인덱스를 통해 원소를 탐색할 수 있다.

순차 리스트는 삽입, 삭제에는 비효율적이지만 탐색에는 효율적이다!

 

선형리스트의 구현

• 사용자가 입력하는 데이터가 가변적으로 작동하는 범용적 코드를 작성해보자.
• 배열의 맨 끝 위치는 len(배열이름)-1로 구할 수 있다.

 

맨 뒤 삽입

1️⃣ 배열 맨뒤에 빈칸 추가

2️⃣ 배열 길이 확인

3️⃣ (배열 길이-1) 위치에 데이터 삽입

 

중간 데이터 삽입

1️⃣ 선형 리스트에 빈칸을 추가

2️⃣ n번째(마지막) 자리에 n-1번쨰 값을을 넣고, n-1번쨰를 빈칸으로 만든다

3️⃣ 지정위치 칸으로 위동할 때까지 위 과정을 반복 ⇒ for문 이용

4️⃣ 지정위치 칸에 새로운 값을 삽입

 

데이터 삭제

1️⃣ 지정 위치(x)의 데이터를 삭제

2️⃣ 지정 위치 바로 다음(x+1)의 데이터를 지정위치(x) 자리로 이동하고 x+1자리는 빈칸으로 만든다.

3️⃣ 배열의 마지막 위치로 이동할 때까지 위 과정을 반복한다 ⇒ for문

4️⃣ 배열의 맨 마지막 위치를 완전히 제거한다.

#선형 스트 = 순차 리스트 (입력 순서대로 저장) 처리 프로그램

#[1] 데이터 삽입

#배열 선언 선형리스트 생성 -> 파이썬 배열로
katok=[] 
select=0

# 데이터 삽입함수 
def add_data(friend):
    katok.append(None)
    length=len(katok)
    katok[length-1]=friend
add_data("성민")
add_data("다현")
add_data("나연")
add_data("나현")
add_data("민영")
print(katok)

# 데이터 삽입함수

def insert_data(position,friend):
    if position<0 or position>len(katok):
        print("데이터를 삽입할 범위를 벗어났습니다.")
        return
    
    katok.append(None) #빈 자리 삽입
    length=len(katok) #현재 배열의 크기
    
    for i in range(length-1,position,-1):
        katok[i]=katok[i-1] # 빈 자리와 교환해서 뒤로 보내기
        katok[i-1]=None #원래 자리를 빈칸으로
    
    katok[position]=friend #지정한 위치에 새로운 값 추가
    print(katok)

# for i in range(값1, 값2, 값3)에서 값1과 값2가 같으면 한 번도 수행하지 않는다.

#작동 테스트
insert_data(3,'다은')

#[2] 데이터 삭제

# 데이터 삭제 함수
def delete_data(position):
    
    if position<0 or position>len(katok):
        print("데이터를 삽입할 범위를 벗어났습니다.")
        return
    
    length=len(katok) #현재 배열의 크기
    katok[position]=None # 데이터 삭제
    
    for i in range(position+1,length):
        katok[i-1]=katok[i] # 뒤의 값을 앞으로 땡겨옴
        katok[i]=None #뒷자리를 다시 빈칸으로
    
    del(katok[length-1])
    print(katok)
    
delete_data(2)

# 메인코드

if __name__=="__main__": # 모듈이 아닌 파이썬 파일을 직접 실행했을 때만 아래 코드를 실행
    while (select!=4):
        select=int(input("메뉴를 선택하세요. 1: 추가, 2: 삽입, 3:삭제, 4:종료"))
        
        if (select==1):
            data=input("추가할 데이터를 입력하세요.")
            add_data(data)
            
        if (select==2):
            pos=int(input("삽입할 위치를 입력하세요."))
            data=input("삽입할 데이터를 입력하세요.")
            insert_data(pos,data)
            
        if(select==3):
            pos=input("삭제할 데이터의 위치를 입력하세요.")
            delete_data(pos)
        
        elif(select==4):
            print(katok)
            exit
            2
            
        else:
            print("1~4 중 하나를 입력하세요.")

 

선형 리스트의 응용

• 선형 리스트는 다항식을 저장하고 활용하는 데에 많이 응용된다.

다항식의 선형 리스트 표현과 계산 프로그램

## 함수 선언 부분 ## 
def printPoly(t_x, p_x) :
	polyStr = "P(x) = "
	
	for i in range(len(p_x)) :
		term = t_x[i]	# 항 차수
		coef = p_x[i]	# 계수

		if (coef >= 0) :		
			polyStr += "+"
		polyStr += str(coef) + "x^" + str(term) + " "

	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

	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)## 함수 선언 부분 ## 

 

 

참고

[자료구조] 선형 리스트 (Linear List)

[이론] 1. 리스트 (List) - 배열, 순차리스트, 연결리스트 (Array, Array List, Linked List)

[자료구조] 순차 리스트(Sequential List) - 윤이네 수선집 개발일기 | Yun's SuSeon Blog