Python: linked list 구현하기

파이썬으로 linked list 구현하기

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

class linkedlist:
    def __init__(self):
        self.END_NODE = Node(None)
        self.head = self.END_NODE
        self.tail = self.END_NODE
        self.current = self.END_NODE
				self.before = None
        self.num_elements = 0
    #None 데이터로 중복으로 충돌하는 것을 방지
		#None 이어도 reference 데이터로 저장

    def get(self):
        if self.current is self.END_NODE and self.head is self.END_NODE:
            return None
				
				if self.current is self.END_NODE and self.tail is self.END_NODE:
						raise Exception("END NODE")
				#비교는 값을 비교하는 == 이 아니라 reference 값까지 비교하는 is 를 이용
				#같은 값이라도 reference 가 달라 중복 값을 처리해준다.   

        return self.current.value
    
    def move_next(self):
        if self.current is self.END_NODE:
            return None
        
        if self.tail is self.END_NODE:
            raise Exception("END NODE")
				#마지막일 node일 경우 오류가 안나도록 예외처리
     
        self.current = self.current.next
        
    def add(self, value):
        new_node = Node(value)
        
        if self.current is self.END_NODE:
						new_node.next = self.current
            self.head = new_node
            self.tail = self.current
            self.current = new_node

        elif self.current is self.head:
							self.head = new_node
							new_node.next = self.current
	            self.current = new_node

        elif self.current is self.tail:
                new_node.next = self.current
								self.current = new_node
	      else:         
            new_node.next = self.current.next
            self.current.next = new_node
						self.before = self.current
            self.current = new_node
						#바뀌는 순서에 주의 -> 순서가 바뀌면 변경된 값이 복사된다
            
        self.num_elements += 1
    
    def delete(self):
				#경우의 수1
        if self.current is self.END_NODE:
            return None
						
        elif self.current is self.tail:
            raise Exception("END NODE")

        elif self.current is self.head:
            self.head = self.current.next
            self.current = self.current.next
            
        else:
						self.before.next = self.current.next
						self.current = self.current.next
        
            
        self.num_elements -= 1
        
    def move_front(self):
        if self.head is self.END_NODE:
            return
        
        self.before = None
        self.current = self.head
        
    def size(self):
        return self.num_elements

→ 단방향 연결리스트

→ END NODE가 존재하는 연결리스트

Linked list로 Array 구현하기

class ListArray:
    def get(self, idx):
        if idx < 0 or idx >= self.size:
            raise Exception("Out of Range!")
        
        else:
            for i in range(idx):
                self.array.move_next()

            value = self.array.get()
            print(value)
            
            self.array.move_front()
        
        
    def set(self, idx, value):
        if idx < 0 or idx >= self.size:
            raise Exception("Out of Range!")
        
        elif idx == 0:
            self.array.add(value)
            self.array.move_front()
            self.array.delete()
				#인덱스가 0일때 삭제 먼저하면 수정이 불가능하기때문에 먼저 데이터 생성후 삭제
        
        else:
            for i in range(idx):
                self.array.move_next()
            self.array.delete()
            self.array.add(value)
            self.array.move_front()
    
    def __init__(self, size):
        self.size = size
        self.array = linkedlist()
        for i in range(size):
            self.array.add(None)
				#None 데이터를 미리 넣어주면서 사이즈 설정
				#중복데이터 처리에 유의 해야함
        self.array.move_front()

Linked list로 stack 구현하기

class ListStack:
    def push(self, value):
        self.stack.add(value)
            
    def pop(self):
				if size == 0:
            return None

        value = self.stack.get()
        self.stack.delete()
				#push만 하면 자동으로 current는 마지막 node
        
        return value
        
    def __init__(self):
        self.stack = linkedlist()

Linked list로 Queue 구현하기

class ListQueue:
    def enqueue(self, value):
				self.queue.add(value)
    
    def dequeue(self):
				if size == 0:
            return None

        self.queue.move_front()
        
        value = self.queue.get()
        self.queue.delete()
				#맨 앞의 값 변수 저장후 삭제
				
				for i in range(size-1):
					self.queue.move_next()
        #사이즈-1 만큼 뒤로 이동

				return value

    def __init__(self):
        self.queue = linkedlist()