CS/자료구조
python으로 LinkedList 만들기
Timha
2023. 8. 30. 21:40
원티드 프리온보드 인턴쉽과정을 학습하면서 링크드 리스트를 배우고 나서 파이썬으로 구현해봤다.
처음에는 직접 리스트를 만든다는게 감이 잘 안왔지만 수업을 보면서 리스트가 어떻게 이뤄지고 어떤 형식으로 움직이는지 알게되고나니 생각보다 만들기 어렵지 않았다.
기본적인 리스트는 head 하나를 가지며 리스트의 헤드를 통해서 각 노드를 순회 할 수 있다.
Node에 데이터를 넣을 data와 next를 통해서 데이터와 다음노드방향을 알려준다.
<코드 본문 >
class Node:
def __init__(self,data):
self.data = data # 노드값
self.next = None # 최초 생성시 다음 노드 지정안함
class LinkedList:
def __init__(self,data): # 최초 링크드리스트 사용시 헤더 생성
self.head = Node(data)
def append(self,data):
cur = self.head # 현재 리스트의 헤드(시작점) 찾기
while cur.next is not None: # 마지막 다음 목적지가 NOne값이 나올떄까지 반복
cur= cur.next
cur.next = Node(data) # 마지막 노드와 현재 추가하려는 노드 연결
def find_index(self,data): #값으로 인덱스 찾기
now =self.head # 헤드부터 시작해서 data값과 동일한 값 찾기
cnt=0
while now == data: # 동일한값을 찾는ㄴ다면 정지
if now.data ==data:
break
cnt+=1
now = now.next
print(cnt)
def get_node(self,data): #인덱스 노드 위치 찾기
now = self.head #리스트의 헤드 찾기
cnt =0
while now>data:
now =now.next
cnt+=1
return cnt
def insert_node(self,index,data): #노드 삽입
new_node = Node(data)
if index==0: # 헤드변경
new_node.next = self.head
self.head = new_node
return
find_node= self.get_node(index-1) # 찾을 인덱스의 전 인덱스 찾기
new_node.next = find_node.next # 생성된 노드의 next를 전 인덱스의 next로 변경
find_node.next = new_node # 찾은 인덱스 -1 의 next를 생성된 노드로 지정
def delete_node(self,index):
if index ==0:
self.head = self.head.next
return
find_node =self.get_node(index-1) # 인덱스-1 를 찾은 후 현재 인덱스의 앞의 연결된 부분을 연결
find_node.next = find_node.next.next # 인덱스 next변경해줌
이번주에 나온 과제중 stack을 만드는 문제가 있었는데 먼저 링크드 리스트를 만들고나니 한결 쉽게 풀 수 있었다.