[Python 자료구조] 연결리스트 (Linked List)

#자료 구조 정의

#노드
class Node:
	def __init__(self.item):
    	self.data = item
        self.next = None
        

#비어있는 연결리스트 
class LinkedList:
	def __init(self)
    		self.nodeCount = 0
            self.head = None
            self.tail = None
            

 

#연산 정의

(1) 특정 원소 참조 (k번째)

#K번째 노드 찾기

#[1][67] -> [2][34] -> [3][58]
# 노드의 개수: 3
#Head: 67
#Tail: 58


def getAt(self, pos):
	if pos <=0 or pos > self.nodeCount: #pos 번째에 있는 노드를 반환하는 것이 목표
    	retrun None #pos가 0보다 작거나 노드 개수보다 작으면 없다.

 

(2) 리스트 순회

    def traverse(self):
        if not self.head:
            return []

        returnList = []
        curr = self.head # 1 

        while curr is not None:
            returnList.append(curr.data) # 67
            curr = curr.next
            
        return returnList

 

(3) 길이 얻어내기

# Node class 
class Node: 
    # Function to initialise the node object 
    def __init__(self, data): 
        self.data = data # Assign data 
        self.next = None # Initialize next as null 
  
  
# Linked List class contains a Node object 
class LinkedList: 
  
    # Function to initialize head 
    def __init__(self): 
        self.head = None
  
  
    # This function is in LinkedList class. It inserts 
    # a new node at the beginning of Linked List. 
    def push(self, new_data): 
  
        # 1 & 2: Allocate the Node & 
        #     Put in the data 
        new_node = Node(new_data) 
  
        # 3. Make next of new Node as head 
        new_node.next = self.head 
  
        # 4. Move the head to point to new Node 
        self.head = new_node 
  
  
    # This function counts number of nodes in Linked List 
    # iteratively, given 'node' as starting node. 
    def getCount(self): 
        temp = self.head # Initialise temp 
        count = 0 # Initialise count 
  
        # Loop while end of linked list is not reached 
        while (temp): 
            count += 1
            temp = temp.next
        return count 

 

(4) 원소 삽입

#원소 삽입
def insertAt(self, pos, newNode):
    if pos < 1 or pos > self.nodeCount + 1:#pos가 올바른 값을 가지는 범위에 없으면
        return False #False를 반환함
    
    if pos == 1: #삽입하려는 위치가 맨 앞일 때 prev가 없음
        newNode.next = self.head #head 조정 필요
        self.head =newNode
        
    else: #삽입하려는 위치가 리스트의 처음이 아니라면
        prev = self.getAt(pos - 1) #직전의 노드를 얻고
        newNode.next = prev.next #삽입되는 노드의 next는 pos - 1 노드의 next로 보냄
        prev.next = newNode #prev의 next링크는 newNode를 가르키도록 조정
        
    if pos == self.nodeCount +1:#삽입하려는 위치가 맨 끝일때 
        self.tail = newNode #tail을 새로운 노드에 가르키도록 조정
        
    self.nodeCount += 1 #self에 +1한 뒤 True를 반환
    return True



#삽입하려는 위치가 맨 끝일때
def insertAt(self, pos, newNode):
    if pos < 1 or pos > self.nodeCount + 1:#pos가 올바른 값을 가지는 범위에 없으면
        return False #False를 반환함
    
    if pos == 1: #삽입하려는 위치가 맨 앞일 때 prev가 없음
        newNode.next = self.head #head 조정 필요
        self.head =newNode
        
    else: 
        if prev = self.getAt + 1:
            prev = self.tail #prev가 self의 tail로 
        else:
            prev = self.getAt(pos -1) #그렇지 않으면 앞에서부터
        newNode.next = prev.next
        prev.next = newNode
        
    if pos == self.nodeCount +1:
        self.tail = newNode 
        
    self.nodeCount += 1 #self에 +1한 뒤 True를 반환
    return True

- 원소 삽입 실습

class Node:

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


class LinkedList:

    def __init__(self):
        self.nodeCount = 0
        self.head = None
        self.tail = None


    def __repr__(self):
        if self.nodeCount == 0:
            return 'LinkedList: empty'

        s = ''
        curr = self.head
        while curr is not None:
            s += repr(curr.data)
            if curr.next is not None:
                s += ' -> '
            curr = curr.next
        return s


    def getAt(self, pos):
        if pos < 1 or pos > self.nodeCount:
            return None

        i = 1
        curr = self.head
        while i < pos:
            curr = curr.next
            i += 1

        return curr


    def insertAt(self, pos, newNode):
        if pos < 1 or pos > self.nodeCount + 1:
            return False

        if pos == 1:
            newNode.next = self.head
            self.head = newNode

        else:
            if pos == self.nodeCount + 1:
                prev = self.tail
            else:
                prev = self.getAt(pos - 1)
            newNode.next = prev.next
            prev.next = newNode

        if pos == self.nodeCount + 1:
            self.tail = newNode

        self.nodeCount += 1
        return True


    def getLength(self):
        return self.nodeCount


    def traverse(self):
        result = []
        curr = self.head
        while curr is not None:
            result.append(curr.data)
            curr = curr.next
        return result


    def concat(self, L):
        self.tail.next = L.head
        if L.tail:
            self.tail = L.tail
        self.nodeCount += L.nodeCount

 

a = Node(67)
b = Node(34)
c = Node(28)
L = LinkedList()
L

#Out: LinkedList: empty

 

 

L.insertAt(1,a)
#Out: True


L.insertAt(2,b)
#Out: True


L
#Out: 67 -> 34


L.insertAt(1,c)
#Out: True


L
#Out: 28 -> 67 -> 34

- 원소 삽입의 복잡도

 맨 앞에 삽입하는 경우 : O(1)

 중간에 삽입하는 경우 : O(n)

 맨 끝에 삽입하는 경우 : O(1)

 

(5) 원소 삭제

- 원소 삭제의 복잡도

 맨 앞에 삭제하는 경우 : O(1)

 중간에 삭제하는 경우 : O(n)

 맨 끝에 삭제하는 경우 : O(n)

 

class Node:

    def __init__(self, item):
        self.data = item
        self.next = None
        
    class LinkedList:
    
        def __init__(self):
            self.nodeCount = 0
            self.head = None
            self.tail = None
            
        def getAt(self, pos):
            if pos < 1 or pos > self.nodeCount:
                return None
            
            i = 1
            curr = self.head
            while i < pos:
                curr = curr.next
                i += 1
            
            return curr
            
        def insertAt(self, pos, newNode):
            if pos < 1 or pos > self.nodeCount + 1:
                return False
                
            if pos == 1:
                newNode.next = self.head
                self.head = newNode
            
            else:
                if pos == self.nodeCount + 1:
                    prev = self.tail
                else:
                    prev = self.getAt(pos-1)
                newNode.next = prev.next
                prev.next = newNode
            
            if pos == self.nodeCount + 1:
                self.tail = newNode
                
            self.nodeCount += 1
            return True
            
            def popAt(self, pos):
                data = 0
                if pos < 1 or pos > self.nodeCount:
                    raise IndexError
                    
                if self.nodeCount == 1:
                    data = self.head.data
                    self.head = None
                    self.tail = None
                    
                else:
                    if pos == 1:
                        data = self.head.data
                        self.head = self.head.next
                        
                    if pos == self.nodeCount:
                        prev = self.getAt(pos-1)
                        data = prev.next.data
                        prev.next = None
                        self.tail = prev
                        
                    else:
                        prev = self.getAt(pos-1)
                        data = prev.next.data
                        prev.next = prev.next.next
                        
                    self.nodeCount -= 1
                    return data
                    
                def traverse(self):
                    result = []
                    curr = self.head
                    while curr is not None:
                        result.append(curr.data)
                        curr = curr.next
                    return result
                    
            def solution(x):
                return 0

 

 

 

(6) 두 리스트 합치기

#두 리스트의 연결
def concat(self,L):
    self.tail.next = L.head #내 끝이 이어 붙이려는 처음
    #내 tail이 이어붙이려는 tail
    #L.tail이 유효한 경우에만 붙임
    if L.tail
        self.tail = L.tail
    self.nodeCount +=L.nodeCount

 

 

 

#Dummy node를 추가한 형태

class Node:

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


class LinkedList:

    def __init__(self):
        self.nodeCount = 0
        self.head = Node(None)
        self.tail = None
        self.head.next = self.tail


    def __repr__(self):
        if self.nodeCount == 0:
        return 'LinkedList: empty'

        s = ''
        curr = self.head
        while curr.next:
            curr = curr.next
            s += repr(curr.data)
            if curr.next is not None:
                s += ' -> '
        return s


    def getLength(self):
        return self.nodeCount

#리스트 순회
    def traverse(self): 
        result = []
        curr = self.head
        while curr.next: #next 링크가 살아있는 한
            curr = curr.next 
            result.append(curr.data) #그 결과를 result리스트에 담는다.
        return result


#K번째 원소 얻어내기
    def getAt(self, pos):
		if pos < 0 or pos > self.nodeCount:
			return None #pos가 0보다 작으면 head 리턴

		i = 0
		curr = self.head
		while i < pos:
			curr = curr.next
			i += 1

		return curr


#원소의 삽입
#[prev]->[prev.next] 
#[prev]->[newNode]->[prev.next] 
	def insertAfter(self, prev, newNode):
		newNode.next = prev.next #newNode의 next링크는 prev.next
		if prev.next is None: #prev.next가 없다면
			self.tail = newNode #tail이 newNode로 옮겨짐
		prev.next = newNode #prev가 가리키는 node의 다음에 newNode 삽입
		self.nodeCount += 1 
		return True #성공/실패에 따라 True/False를 리턴


	def insertAt(self, pos, newNode):
		if pos < 1 or pos > self.nodeCount + 1:
			return False

		if pos != 1 and pos == self.nodeCount + 1:
			prev = self.tail
		else:
			prev = self.getAt(pos - 1)
		return self.insertAfter(prev, newNode)


	def concat(self, L):
		self.tail.next = L.head.next
		if L.tail:
			self.tail = L.tail
		self.nodeCount += L.nodeCount

 

(1) 길이 얻어내기

 

(2) 리스트 순회

#리스트 순회
    def traverse(self): 
        result = []
        curr = self.head
        while curr.next: #next 링크가 살아있는 한
            curr = curr.next 
            result.append(curr.data) #그 결과를 result리스트에 담는다.
        return result

 

(3) 특정 원소 참조 (k번째)

#K번째 원소 얻어내기
    def getAt(self, pos):
		if pos < 0 or pos > self.nodeCount:
			return None #pos가 0보다 작으면 head 리턴

		i = 0
		curr = self.head
		while i < pos:
			curr = curr.next
			i += 1

		return curr

#pos범위 조건 확인
	def insertAt(self, pos, newNode):
		if pos < 1 or pos > self.nodeCount + 1:
			return False
        
#pos == 1인 경우에는 head 뒤에 새 node 삽입
#pos == nodeCount +1인 경우에는 prev <- tail
		if pos != 1 and pos == self.nodeCount + 1:
			prev = self.tail
#그렇지 않은 경우에는 prev <- getAt(...)
		else:
			prev = self.getAt(pos - 1)
		return self.insertAfter(prev, newNode)

 

(4) 원소 삽입

#원소의 삽입
#[prev]->[prev.next] 
#[prev]->[newNode]->[prev.next] 
	def insertAfter(self, prev, newNode):
		newNode.next = prev.next #newNode의 next링크는 prev.next
		if prev.next is None: #prev.next가 없다면
			self.tail = newNode #tail이 newNode로 옮겨짐
		prev.next = newNode #prev가 가리키는 node의 다음에 newNode 삽입
		self.nodeCount += 1 
		return True #성공/실패에 따라 True/False를 리턴

 

(5) 원소 삭제

            def popAt(self, pos):
                data = 0
                if pos < 1 or pos > self.nodeCount:
                    raise IndexError
                    
                if self.nodeCount == 1: 
                    data = self.head.data
                    self.head = None
                    self.tail = None
                    
                else:
                    if pos == 1:
                        data = self.head.data
                        self.head = self.head.next
                        
                    if pos == self.nodeCount:
                        prev = self.getAt(pos-1)
                        data = prev.next.data
                        prev.next = None
                        self.tail = prev
                        
                    else:
                        prev = self.getAt(pos-1)
                        data = prev.next.data
                        prev.next = prev.next.next
                        
                    self.nodeCount -= 1
                    return data

 

(6) 두 리스트 합치기

#두 리스트의 연결
	def concat(self, L):
		self.tail.next = L.head.next
		if L.tail:
			self.tail = L.tail
		self.nodeCount += L.nodeCount