연결리스트(linked list)

: 노드(node)가 링크(link)에 의해 기차처럼 연결된 순차(sequential) 자료구조

  • Node = key(데이터 값) + link

    => 메모리상에 흩어져 있음 (node와 link로 연결)

  • 장점 : 삽입(insert)이 O(1)시간으로 매우 빠름

    ​ -> 넣을 곳 앞 뒤의 link만 바꿔주면 되기 때문( 단, 앞 뒤를 알고 있어야 함)

  • 단점 : 읽기는 head node부터 link 따라가야함 image

    한방향 연결리스트(singly Linked List)

    : 노드들이 한쪽방향으로만(next 링크 따라) 연결된 리스트

    # 노드클래스
    class Node: 
    	def __init__(self, key=None, value=None):
    		self.key = key   # 노드를 다른 노드와 구분하는 key값
    		self.value = value #필요한 경우 추가 데이터 value
    		self.next = None	# 다음 노드로의 링크(초기값은 None)
      		
    	def __str__(self): 	#print(node)인 경우 출력할 문자열
    		return str(self.key) 	#str((self.key, self, value))
      
    # 한방향연결리스트 클래스
    class SinglyLinkedList:
    	def __init__(self):
    		self.head = None	# 연결리스트의 가장 앞의 노드 (head)
    		self.size = 0		# 리스트의 노드 개수
      		
    	def __iter__(self): # generator 정의
        	v = self.head	
    		while v != None: 
    			yield v
    			v = v.next
                  
    	def __str__(self): # 연결 리스트의 값을 print
    		return " -> ".join(str(v) for v in self)
              
    	def __len__(self):
    		return self.size
    
  • 지원 연산

    L = SinglyLinkedList()

    [삽입]

    1. L.pushFront(key) : key 값을 갖는 새 노드를 L의 가장 앞에 삽입

      -> L.head가 변경되야함

    2. L.pushBack(key) : key 값을 갖는 새 노드를 L의 가장 뒤에 삽입

    [삭제]

    1. L.popFront(): L의 첫 노드(head 노드) 삭제 & key 리턴

    2. L.popBack() : L의 마지막 노드 삭제 & key 리턴

    3. L.remove(v) : L에서 노드 v를 제거

    [찾기]

    1. L.search(key): L에서 key 값을 갖는 노드를 찾아 리턴
  • pushFront

def pushFront(self,key):
	new_node = Node(key, value)  # 새 노드 생성
	new_node.next = self.head
	self.head = new_node
	self.size += 1
  • pushBack

    def pushBack(self, key, value = None):
    	new_node = Node(key, value) #새 노드 생성
    	if self.size == 0: #empty list
    		self.head = new_node 
    	else: 	# 빈 리스트가 아니면
    		tail = self.head
    		while tail.next != None: #tail 찾기
    			tail = tail.next
    		tail.next = new_node
    	self.size += 1
    
  • popFront

    def popFront(self):
    	if self.size == 0: #or len(self) == 0
    		return None
    	else: 
    		x = self.head
    		key = x.key
    		self.head = x.next
    		self.size = self.size - 1
    		del x
    		return key
      
    
  • popBack

    def popBack(self):
    	if self.size == 0: #노드가 하나도 없는 경우
    		return None
    	else:
    		prev, tail = None, self.head
    		while tail.next != None:
    			prev = tail
    			tail = tail.next
    		if prev == None: #노드가 한개만 있을 때
    			self.head == None
    		else:
    			prev.next = None
    		key = tail. key
    		del tail
    		self.size -= 1
    		return key
    
  • search(key)

    [while]

    def search(self, key):
    	v = self.head
    	while v != None:
    		if v.key == key:
    			return v
    		v = v.next
    	return v
    

    [for]

    def search(self,key):
    	for v in self:
    		if v.key == key:
    			return v
    	return None
    

    [generator] –> 찾기 연산시 for 사용하면 됨

    def __iterator__(self):
    	v = self.head
    	while v != None:
    		yield v      #for문에 대입해 None만나도록(stopiterator 로 for루프 중단)     
    		v = v.next
    # for x in L:
    #	print(x)
    
  • remove(v)

    def remove(self, v):
    	if self.size == 0: # 빈리스트
    		return None
    	else:
    		prev, x = None, self.head
    		while x.next != None:
    			prev = x
    			x = x.next
    		if prev == None: # 노드가 하나
    			self.popFront(x)
    		else:
    			prev.next = x.next
    			del x