[자료구조] 링크드 리스트 : 추가연산 , 접근연산

링크드 리스트

- 데이터를 순서대로 저장해준다.

- 요소를 계속 추가할 수 있다.

 

 

링크드 리스트 만들기 실습

class Node:
"""링크드 리스트의 노드 클래스"""

	def __init__(self, data):
    	self.data = data #노드가 저장하는 데이터
        self.next = None # 다음 노드에 대한 래퍼런스
   
#데이터 2, 3, 5, 7, 11 을 담는 노드들 생성
head_node = Node(2)
node_1 = Node(3)
node_2 = Node(5)
node_3 = Node(7)
tail_node = Node(11)

#노드들을 연결
head_node.next = node_1
node_1.next = node_2
node_2.next = node_3
node_3.next = tail_node

#노드 순서대로 출력
iterator = head_node

while iterator is not None:
	print(iterator.data)
    iterator = iterator.next

 

링크드 리스트 만들기 실습 출력

2
3
5
7
11

 

링크드 리스트 추가 연산, 접근 연산 실습

 

* 접근연산

- 특정 위치에 있는 노드를 리턴하는 연산

- 래퍼런스를 통해 위치를도달하기 떄문에 한번에 원하는 위치의 데이터에 접근할 수 없음

- 시간 복잡도 : O(n)

class Node:
"""링크드 리스트의 노드 클래스"""

	def __init__(self, data):
    	self.data = data #노드가 저장하는 데이터
        self.next = None # 다음 노드에 대한 래퍼런스
       
class LinkedList:
"""링크드 리스트 클래스"""

	def __init__(self):
    	self.head = None
        self.tail = None
	
    def find_node_at(self, index):
    	"""링크드 리스트 접근 연산 메소드, 파라미터 인덱스는 항사 있다고 가정"""
        iterator = self. head
        
        for _ in range(index):
        	iterator = iterator.next
         return iterator
    
    def append(self, data):
    	"""링크드 리스트 추가 연산 메소드 """
        new_node = Node(data)
        
        if self.head is None: #링크드 리스트가 비어 있는 경우
        	self.head = new_node
            self.tail = new_node
        else: #링크드 리스트가 비어 있지 않은 경우
        	self.tail.next = new_node
            self.tail = new_node
            
#새로운 링크드 리스트 생성
my_list = LinkedList()

#링크드 리스트에 데이터추가
my_list.append(2)
my_list.append(3)
my_list.append(5)
my_list.append(7)
my_list.append(11)

#링크드 리스트 노드에 접근 (데이터 가져오기)
print(my_list.find_node_at(3).data)

#링크드 리스트 노드에 접근 (데이터 바꾸기)
my_list.find_node_at(2).data =13

#노드 순서대로 출력
iterator = my_list.head

while iterator is not None:
	print(iterator.data)
    iterator = iterator.next

 

링크드 리스트 접근연산 실습 출력

2
3
13
7
11