[LeetCode/Linked List] Design Linked List

[LeetCode/Linked List] Design Linked List

[문제]

https://leetcode.com/explore/learn/card/linked-list/209/singly-linked-list/1290/

[어려웠던 점]

- 다짜고짜 연결리스트의 삽입/삭제/탐색 구현하라고 해서 그냥 당황스러웠어요....

[정답 코드]

class Node:# 노드 클래스 생성 def __init__(self,val):# java의 생성자 같은 느낌 self.val=val self.next=None class MyLinkedList: # 초기화 def __init__(self): self.head=None self.size=0 # index로 val 리턴 받기, 해당하는 인덱스가 없다면 -1 반환 def get(self, index: int) -> int: if index < 0 or self.size <= index: #size보다 같은 것도 안 됨 return -1 cur=self.head #head에서 시작 for _ in range(index): cur=cur.next return cur.val # head 노드 추가하기 def addAtHead(self, val: int) -> None: self.addAtIndex(0,val) # 마지막에 노드 추가하기 def addAtTail(self, val: int) -> None: self.addAtIndex(self.size,val) # 해당 index에 노드 추가하기, index가 length와 같다면 addAtTail(), index가 length보다 크면 실패 def addAtIndex(self, index: int, val: int) -> None: # index가 length보다 크면 실패 if index > self.size: return cur = self.head new_node=Node(val) #추가하고자 하는 노드 생성 # index가 0인 경우 head에 추가 if index == 0: #원래 self.head가 값이 있거나 없는 상황을 나눴지만 만약 # self.head가 없다면 어차피 None이니까 그냥 해도 됨 new_node.next=cur self.head=new_node # index 1 이상 else: # index가 3이면 index-1=2, for문은 0,1 도니까 2에 가있음 for _ in range(index-1): cur=cur.next #cur.next는 현재 index 3에 있는 것을 말함 new_node.next=cur.next #이제 바꿔줌 cur.next=new_node self.size+=1 # 해당 index가 있다면 val 삭제 def deleteAtIndex(self, index: int) -> None: # index 오류 if index<0 or self.size <= index: return # index가 0이면 head 삭제 if index == 0: self.head=self.head.next # index 1 이상 else: cur=self.head # 삭제하고자 하는 인덱스 전까지 간 후 for i in range(index-1): cur=cur.next #cur.next.next는 현재 index 2니까 index 4 노드를 말함 cur.next=cur.next.next self.size-=1 # Your MyLinkedList object will be instantiated and called as such: # obj = MyLinkedList() # param_1 = obj.get(index) # obj.addAtHead(val) # obj.addAtTail(val) # obj.addAtIndex(index,val) # obj.deleteAtIndex(index)

주석으로 써가면서 최대한 답을 안 보고 작성해보려고 노력했습니다.

[배운 것]

- class 정의하는 걸 코테 준비하면서 해본 적이 없는데 배웠습니다.

- 연결 리스트 구현하는 걸 전반적으로 익혔습니다.

from http://juyeonee826.tistory.com/79 by ccl(A) rewrite - 2021-08-31 02:26:43