선형 리스트[Linear List] 란?
데이터를 일정한 순서로 나열한 자료구조로 '순차 리스트' 라고도 한다.
즉, 선형 리스트는 입력으로 들어온 데이터들이 순차적으로 저장되는 형식이라고 볼 수 있다.
가장 기본적으로 배열(리스트)을/를 통해 구현한다.
선형 리스트의 장점
- 데이터가 실제 위치 순서로 구성되기 때문에 데이터를 파악하기 쉽다. (직관적이다)
- 구현이 간단하다.
- 인덱스를 이용해 데이터에 접근할 수 있으므로 접근성이 좋다.
선형 리스트의 단점
- 삽입/삭제 시 시간이 오래걸린다. (O(N)의 속도를 가진다)
- 배열을 만들 때 데이터의 크기가 고정적이기 때문에 낭비하는 공간이 생길 수 있다.
선형 리스트의 간단한 구현
delivery = ["치킨", "피자", "햄버거", "None", "None"]
for food in range(len(delivery)):
print(delivery[food], end=" " )파이썬을 이용해 구현한 선형리스트
CODE RESULT
치킨 -> 피자 -> 햄버거 -> (공백) -> (공백)
이처럼 선형리스트는 리스트에 입력된 데이터가 순서대로 저장되는 것을 알 수 있다.
선형리스트의 데이터 삽입
선형리스트의 데이터 삽입은 크게 2가지로 나눌 수 있다.
1) 리스트의 빈 공간 / 맨 뒤에 데이터를 삽입하는 경우
delivery = ["치킨", "피자", "햄버거", "None", "None"]
delivery[4] = "족발"
for food in range(len(delivery)):
print(delivery[food], end=" " )리스트의 빈 공간 / 맨 뒤에 데이터를 삽입할 때
그림과 같이 리스트의 맨 뒤에 데이터를 삽입하는 경우에는 맨 뒤에 데이터를 넣기만 하면 되는 것이므로
O(1)의 시간복잡도를 가진다.
2) 리스트의 맨 앞 / 중간에 데이터를 삽입하는 경우
delivery = ["치킨", "피자", "햄버거", "None", "None"]
position = 1 # 데이터를 삽입할 위치
for i in range(len(delivery)-1, position, -1):
delivery[i] = delivery[i-1]
delivery[i-1] = None
delivery[position] = "족발"
for food in range(len(delivery)):
print(delivery[food], end=" ")리스트의 맨 앞 / 중간에 데이터를 삽입할 때
그림과 같이 리스트의 맨 앞 / 중간에 데이터를 삽입하는 경우에는 삽입할 위치를 기준으로 뒤쪽에 있는 데이터들을 한칸씩 뒤로 밀어야 하기 때문에 O(N)의 시간복잡도를 가진다.
선형리스트의 데이터 삭제
선형리스트의 데이터 삭제도 삽입과 마찬가지로 크게 2가지로 나눌 수 있다.
1) 리스트의 맨 뒤의 데이터를 삭제하는 경우
delivery = ["치킨", "피자", "햄버거", "족발", "None"]
delivery[3] = None
for food in range(len(delivery)):
print(delivery[food], end=" ")리스트의 맨 뒤의 데이터를 삭제하는 경우
그림과 같이 리스트의 맨 뒤의 데이터를 삭제하는 경우에는 데이터를 그냥 삭제만 하면 되는 것이므로
O(1)의 시간복잡도를 가진다.
2) 리스트의 맨 앞 / 중간의 데이터를 삭제하는 경우
delivery = ["치킨", "피자", "햄버거", "족발", "None"]
position = 1 # 삭제할 데이터 위치
for i in range(position+1, len(delivery)):
delivery[i-1] = delivery[i]
delivery[i] = None
for food in range(len(delivery)):
print(delivery[food], end=" ")리스트의 맨 앞 / 중간의 데이터를 삭제하는 경우
그림과 같이 리스트의 맨 앞 / 중간의 데이터를 삭제하는 경우에는 삭제할 위치를 기준으로 뒤쪽에 있는 데이터들을 한칸씩 앞으로 당겨줘야 하기 때문에 O(N)의 시간복잡도를 가진다.
선형리스트의 일반적인 구현
데이터 삽입 & 삭제 함수
# 데이터 삽입
def insert_data(data, position):
if position < 0 and position > len(delivery):
print("유효한 위치가 아닙니다!")
return
# 맨 뒤에 데이터를 삽입하는 경우
if position == len(delivery)-1:
delivery[position] = data
return
# 맨 앞 / 중간에 데이터를 삽입하는 경우
else:
for i in range(len(delivery)-1, position, -1):
delivery[i] = delivery[i-1]
delivery[i-1] = None
delivery[position] = data
for food in range(len(delivery)):
print(delivery[food], end=" ")
return
# 데이터 삭제
def delete_data(position):
if position < 0 and position > len(delivery):
print("유효한 위치가 아닙니다!")
return
# 맨 뒤의 데이터를 삭제하는 경우
if position == len(delivery)-1:
delivery[position] = None
return
# 맨 앞 / 중간의 데이터를 삭제하는 경우
else:
for i in range(position+1, len(delivery)):
delivery[i-1] = delivery[i]
delivery[i] = None
for food in range(len(delivery)):
print(delivery[food], end=" ")
return
메인 함수
if __name__ == "__main__":
delivery = ["치킨", "피자", "햄버거", "족발", "None"]
position = int(input("데이터를 삽입할 위치를 입력하세요 ")) # 삽입할 데이터 위치
data = input("삽입할 데이터가 무엇인가요? ")
insert_data(data, position)
print()
delivery = ["치킨", "피자", "햄버거", "족발", "None"]
position = int(input("데이터를 삭제할 위치를 입력하세요 ")) # 삭제할 데이터 위치
delete_data(position)CODE RESULT
정상적으로 데이터가 삽입 & 삭제가 된 모습을 볼 수 있다.
