파이썬 링크드리스트로 배열 구현하기 (자료구조 변환)
파이썬 링크드리스트로 배열 구현하기 (자료구조 변환) — #링크드리스트 #리스트어레이 #listarray #자료구조변환 AI스쿨 msa기반 java 백엔드 코스 중에 공부한 ...
#링크드리스트 #리스트어레이 #listarray #자료구조변환
AI스쿨 msa기반 java 백엔드 코스 중에 공부한 내용을 작성하였습니다
자료구조 변환
이전글을 통해 파이썬으로 배열, 링크드리스트, 스택, 큐 등의 자료구조를 구현해보았습니다. 이번에는 구현된 자료구조를 이용하여 다른 자료구조로 변환하는 작업을 해볼까 합니다.
예를들어 스택을 구현한다고 가정하면, 배열을 사용하여 스택을 구현하거나 큐로 스택을 구현하는 등의 방법입니다.
스택, 큐, 배열, 링크드리스트 순으로 글이 올라올 예정이며, 다른 자료구조로 각각의 자료구조를 어떻게 구현할 수 있는지 정리할겁니다.
링크드 리스트로 배열 구현하기
ListArray
스택과 큐에 대한 자료변환 구현이 끝이났습니다. 이번에는 배열을 구현해볼건데요. 링크드리스트, 스택, 큐로 배열을 구현할겁니다. 각 자료구조의 특징은 이전글을 참고해주세요.
사용할 링크드리스트
이전글을 통해 구현된 링크드 리스트입니다. 처음 보기에 코드가 복잡 할 수 있으니 제공된 링크에서 어던 방법으로 구현되었는지만 이해하고 진행해주세요!
| class Node: def \_\_init\_\_(self, data): self.data = data self.next = Noneclass LinkedList: def \_\_init\_\_(self): self.head = None self.current = None def move\_next(self): # 다음 위치로 이동 if self.current is None: return self.current = self.current.next def get(self): # 현재 위치 가져오기 if self.current is None: return None return self.current.data def modify(self, value): # 현재 위치 값 수정하기 if self.current is None: return self.current.data = value def add(self, value): # 현재 위치의 바로 앞에 추가하기 prev\_node = None if self.current is not self.head: prev\_node = self.head while prev\_node.next != self.current: prev\_node = prev\_node.next new\_node = Node(value) new\_node.next = self.current if self.current is not self.head: prev\_node.next = new\_node else: self.head = new\_node self.current = new\_node def delete(self): # 현재 위치 삭제하기 if self.current is None: return prev\_node = None if self.current is not self.head: prev\_node = self.head while prev\_node.next != self.current: prev\_node = prev\_node.next if self.current is not self.head: prev\_node.next = self.current.next else: self.head = self.current.next self.current = self.current.next def move\_front(self): # 맨 앞으로 이동하기 self.current = self.head |
|---|
ListArray선언하기
\_\_init\_\_
| class ListArray: def get(self, idx): pass def set(self, idx, value): pass def \_\_init\_\_(self, size): self.link = LinkedList() for i in range(size): self.link.add(None) |
|---|
ListArray의 본질은 Array(배열)입니다. 배열의 크기 및 초기값을 설정해야합니다.
우선 생성자에서 LinkedList를 선언한 후, size를 입력값으로 받아와 size만큼 LinkedList에 넣어줍니다.
| linkarray = ListArray(5) |
|---|
linkarry로 ListArray를 선언하면서 size를 넘겨주면 초기값 셋팅 완료입니다.
LinkedList add구조
현재 사용하는 LinkedList의 특징은 add를 해준 value가 뒤로 쌓이는 구조입니다.
예를들어 new\_value... -> third -> second -> first -> None 이런 형태입니다.
저는 이 LinkedList가 first -> second -> third -> ... new\_value -> None 형태로 값이 추가되도록 구현할겁니다.
| class ListArray: def get(self, idx): pass def set(self, idx, value): pass def \_\_init\_\_(self, size): self.link = LinkedList() self.link.add(None) for i in range(1, size - 1): self.link.move\_next() self.link.add(None) |
|---|
제일 처음엔 None 상태기 때문에 바로 값을 넣습니다.
이후 추가되는 값은 new\_value(current) -> None 형태로 쌓이니 new\_value -> None(current) 형태로 만들어주는겁니다. 즉, 항상 현재 포인터를 None에 두는 것이 목표입니다.
이렇게되면 두번째 값이 추가될때는 first -> second(current) -> None 형태가되고 세번째값이 추가될때는 first -> second -> None(current) / first -> second -> third(current) -> None 형태가 될겁니다.
비로써 first -> second -> third -> ... new\_value -> None 원하는 구조가 만들어졌습니다.
ListArray.get(idx)
어떻게 idx를 적용시킬 것인가.
자 우리가 선언된 link를 보기 쉽게 정리해 보겠습니다. 현재 None상태에서 10개의 None값을 가진 노드가 추가로 생성되었습니다.
*None -> None -> None -> None -> None -> None -> None -> None -> None -> None(current) -> **None(끝 값의 다음 값)*
10개의 None이 추가되면서 10번째의 위치에 current가 위치해 있습니다. 항상 끝값의 다음값은 None이기에 위에서는 11개의 None이 표현된걸 볼 수 있습니다.
LinkedList는 index값이 존재하지 않습니다. 오직 현재값과 다음값(혹은 이전값)을 읽을 수 있을 뿐이죠. 그렇기 떄문에 ListArray.get(Idx)을 구현할때는 다음과 같은 방법을 고려할 수 있습니다.
먼저 맨 앞으로 이동 후, 주어진 idx - 1만큼 다음으로 이동하는 방법입니다. 코드를 구현하면 다음과 같습니다.
| class ListArray: def get(self, idx): self.link.move\_front() if idx == 0: self.link.get() else: for i in range(idx - 1): self.link.move\_next() self.link.get() def set(self, idx, value): pass def \_\_init\_\_(self, size): self.link = LinkedList() self.link.add(None) for i in range(1, size - 1): self.link.move\_next() self.link.add(None) |
|---|
idx == 0인 경우에는 반복문의 범위가 벗어나기 때문에 바로 현재 값을 읽어주고, idx == 1 부터는 idx - 1만큼 이동해준 후 현재값을 읽습니다.
ListArray.set(idx, value)
LinkedList.modify(value)를 이용!
마지막으로 ListArray의 값을 바꾸는 set(idx, value)을 구현해야합니다. idx는 get에서 구현한 방법을 그대로 쓰면 되고 값을 바꿀 때는 LinkedList에 구현되어있는 modify(value)함수를 사용합니다.
| class ListArray: def get(self, idx): self.link.move\_front() if idx == 0: self.link.get() else: for i in range(idx - 1): self.link.move\_next() self.link.get() def set(self, idx, value): self.link.move\_front() if idx == 0: self.link.modify(value) else: for i in range(idx - 1): self.link.move\_next() self.link.modify(value) def \_\_init\_\_(self, size): self.link = LinkedList() self.link.add(None) for i in range(1, size - 1): self.link.move\_next() self.link.add(None) |
|---|
자료구조 총정리