자료구조와 알고리즘 파트4. 링크드 리스트(Linked List) 구현

3을 가진 노드 만들기

1) 클래스 정의하기

class Node:
	def __init__(self, data):
    	self.data = data
        self.next = None

• Node 라는 클래스를 만들어서 data를 받아 클래스 내부 변수인 self.data에 받은 data 저장
• 현재는 self.data 하나밖에 없기 때문에 다음 노드는 None인 상태

2) 현재 노드에 값 넣기

node = Node(3)

print(node)
print(node.data)

• print(node) : # xx 주소를 가진 클래스 노드가 생성되었음을 알 수 있다.
• print(node.data) : xx 주소를 가진 클래스 노드의 값이 무엇인지 알 수 있다.
  
  

여러 개의 노드를 연결해보기

1) 클래스 정의하기

class Node:
	def __init__(self, data):
    	self.data = data
        self.next = None

2) 5와 12라는 값을 들고 있는 노드 만들기

first_node = Node(5)
second_node = Node(12)

• first_node = Node(5) : next가 없이 하나의 노드만 존재한다. [5]
• second_node = Node(12) : [12]를 가진 노드를 만든다.

3) 두 노드를 연결하기

first_node.next = second_node

• [5]의 next를 [12]로 지정한다.
  [5] -> [12]
  
  

• 노드의 숫자가 많아지고 일일이 연결하려면 반복해서 변수를 지정하기 번거롭기 때문에 LinkedList 라는 이름의 클래스를 만든다!

LinkedList 클래스 만들기

• 위의 클래스 Node에 이어서 작업
• 다음 노드를 확인하기 위해 각 노드의 next를 조회해서 찾아가야 한다.

1) 클래스 정의하기

class LinkedList:
	def __init__(self, value):
    	self.head = Node(value)

• LinkedList는 self.head에 시작하는 클래스 노드를 저장한다.

2) 출력해보기

linked_list = LinkedList(5)
print(linked_list.head.data) # 5

• 현재 LinkedList 는 5 만 존재한다.

새로운 노드를 붙이기

• LinkedList 의 맨 뒤에 새로운 Node를 붙이는 함수
• 가장 맨 뒤의 노드까지 이동해야 한다.

how to

1. head
   [3] -> [5] -> [6] -> [8]

• head를 따라서 계속 이동
• head를 변경시킬 수 없으니 cur 변수를 이용

2. cur = self.head
   cur
   [3] -> [5] -> [6] -> [8]

3. cur = cur.next
   ----->cur
   [3] -> [5] -> [6] -> [8]

4. cur = cur.next
   ------------->cur
   [3] -> [5] -> [6] -> [8]

5. cur = cur.next
   -------------------->cur
   [3] -> [5] -> [6] -> [8]

6. -------------------->cur___cur.next
   [3] -> [5] -> [6] -> [8] -> None

1) 클래스 정의하기

class Node:
	def __init__(self, value):
    	self.data = value
        self.next = None
        
class LinkedList:
	def __init__(self, value):
    	self.head = Node(value)

2) 새로운 노드 연결

    def append(self, value)
  		cur = self.head
  		while cur.next is not None:
  			cur = cur.next
  		cur.next = Node(data)

3) 예외처리

• 만약 head 가 value 가 아니라 None 이라면?

    def append(self, value)
  		if self.head is None:
  			self.head = Node(data)
  			return

  		cur = self.head
  		while cur.next is not None:
  			cur = cur.next
  		cur.next = Node(data)

4) 노드 연결 해보기

linked_list = LinkedList(3)
linked_list.append(5) # [3] -> [5] 형태로 노드를 연결
linked_list.append(6) # [3] -> [5] -> [6] 형태로 노드를 연결
linked_list.append(8) # [3] -> [5] -> [6] -> [8] 형태로 노드를 연결

5) LinkedList 의 모든 원소 출력하기

	def print_all(self, value)
  		cur = self.head
  		while cur is not None:
  			print("cur is ", cur.data)
  			cur = cur.next

# cur is  3
# cur is  5
# cur is  6
# cur is  8

---

6) LinkedList 의 특정 원소 찾기

    def get_node(self, index):
        cur = self.head
        count = 0
        while count < index:
            cur = cur.next
            count += 1
        return cur.data

linked_list = LinkedList(5)
linked_list.append(12)
print(linked_list.get_node(0))  # 5

• next node로 가는 것을 index번 해야한다.
• count가 index로 될 때까지 cur의 next 값을 cur 에 대입하고 count를 증가
• 이 과정을 count가 index가 아닐때까지 반복
  

7) LinkedList 의 특정 위치에 특정 원소 추가

	def add_node(self, index, value):
        new_node = Node(value)
        if index == 0:
            new_node.next = self.head
            self.head = new_node
            return

        node = self.get_node(index-1)
        next_node = node.next
        node.next = new_node
        new_node.next = next_node

• 만약 index 가 0 이면 -1 이 되니까 if ~ 예외처리를 해준다.
• self.head = new_node 가
  new_node.next = self.head 보다 빨리 오면 뒤에 있는 node들이 다 사라져서 주의!

8) LinkedList 의 특정 위치에 특정 원소 삭제

	def delete_node(self, index):
        if index == 0:
            self.head = self.head.next
            return
        node = self.get_node(index - 1)
        node.next = node.next.next

    def delete_node(self, index):
	node = self.get_node(index - 1)
        del_node = node.next
        if index == 0:
            self.head = del_node
            return
        next_node = del_node.next
        node.next = next_node

• 두번째 코드는 본인 작성
• 결과는 같지만 코드가 두줄 더 길다