[자료구조] 링크드리스트

링크드리스트(연결리스트)

• 배열은 연결된 공간의 크기를 미리 지정해놓아야 사용 할 수 있으며 그 크기를 변경할 수 없다. 따라서 데이터를 추가/삭제 하기가 어렵다.
• 링크드리스트는 이런 문제점을 해결 할 수 있다.
  
• 노드(데이터+포인터)로 구성됨
• 포인터가 다음 노드의 주소값을 참고한다
• 단점 :
  연결을 위한 별도의 공간(포인터)가 필요하므로 저장공간 효율이 높지 않음
  연결 정보를 찾는 시간이 필요하므로 접근 속도가 느림
  중간 데이터 삭제 시, 앞뒤 데이터의 연결을 재구성 해야함

파이썬으로 링크드리스트 구현해보기

class Node:
	#파이썬 함수에서는 항상 첫번째 파라미터로 self를 가진다.
    	#self가 굳이 필요 없을 때도 self를 가진다.
	def __init__(self,data,next=None):
    		self.data=data
            	self.next=next

node1=Node(1)
node2=Node(2)
node1.next=node2 #node1 뒤에 node2를 연결
head=node1 #head라는 변수에 node1 지정

class Node:
	#파이썬 함수에서는 항상 첫번째 파라미터로 self를 가진다.
    	#self가 굳이 필요 없을 때도 self를 가진다.
	def __init__(self,data,next=None):
    		self.data=data
            	self.next=next
                
        def add(data):
        	node = head
      #node.next=None이 아닐때까지 node를 다음 node로 바꿔준다
     	        while node.next: 
            		node = node.next
      #마지막 node의 next에 새로운 node를 넣어준다.
                node.next=Node(data) 

node1 = Node(1)
head = node1
for i in range(2,10):
	add(i)

node = head
while node.next:
	print(node.data)
        node=node.next #node를 다음노드로 바꿔줌
print(node.data) #node.next=None일때 = 마지막 노드 데이터 출력

링크드리스트 사이에 데이터 추가

node = head
while node.next:
	print(node.data)
    	node=node.next
print(node.data)
#1 2 3 4 5 6 7 8 9

#Node(1.5)를 Node(1)과 Node(2) 사이에 추가하고 싶음
node3 = Node(1.5)
node = head
search = True
#node.data==1일때까지 node를 하나씩 뒤로 옮겨가면서 찾는다
while search:
	if node.data==1:
    		search=False
    	else:
        	node=node.next
#node.data==1 이 되면, node.next(기존에 연결된 node)를 push_out_node(뒤로밀려나는) 변수에 저장
push_out_node = node.next
#node.data==1인 node의 next에 node3을 참조하게함
node.next=node3
#node3.next에 push_out_node 참조하게함
node3.next=push_out_noe

파이썬 객체지향 프로그래밍으로 링크드리스트 구현하기

Class Node:
	def __init__(self,data,next=None):
    		self.data=data
            	self.next=next
Class NodeMgmt:
	def __init__(self,data):
    		#데이터를 받아서 첫번째 노드를 만든다
    		self.head=Node(data)
        #다음 노드를 더하는 함수
    	def add(self,data):
#만약 self.head가 없다면 받아온 데이터로 node를 만들고 slef.head에 넣는다
        	if self.head='':
            		self.head=Node(data)
#self.head가 있다면 node.next가 None일때까지 node를 다음 node로 바꾸고, 마지막 node의 next에 새로운 node를 참조하게한다
                else:
                node=self.head
                	while node.next:
                    		node=node.next
                        node.next=Node(data)
        #처음부터 끝까지 순회하는 함수
    	def desc(self):
    		node=self.head
    		while node:
            		print(node.data)
                	node=node.next

링크드리스트 특정 노드 삭제 구현

def delete(self,data):
#self.head가 없다면 (링크드리스트가 구현되지 않았다면) 당연히 data값을 node.data로 가지는 노드는 없음
	if self.head=='':
    		print("해당 값을 가진 노드가 없습니다")
            	return
#node.head를 지우는 경우
    	if self.head.data==data:
        #self.head에 두번째 노드를 넣고, 첫번째 노드를 지운다
        	deleted_soon = self.head
                self.head=self.head.next
                del deleted_soon
#두번째이상의 노드를 지우는 경우
	else:
    	    node=self.head
            while node.next:
                if node.next.data==data
                    delete_soon = node.next
                    node.next=node.next.next
                    del delete_soon
                    return
                else:
                    node=node.next         

노드 데이터가 특정 숫자인 노드를 찾는 함수 만들기

def search_node(self,data):
	node=self.head
    while node:
        if node.data==data:
            return node
        else:
            node=node.next

더블 링크드리스트

• 링크드리스트는 맨 첫 노드부터 찾을 수 밖에 없음
• 내가 원하는 데이터가 8000번째 데이터라면?
• 1번 노드부터 8000번 노드까지 8000번 데이터를 찾아봐야함
• 더블 링크드리스트 : 양방향으로 연결되어 있어서 노드 탐색이 양쪽으로 가능
• 내가 원하는 데이터가 뒷쪽에 있으면 뒤쪽 부터 데이터 탐색 가능
  

class Node:
    def __init__(self,data,prev=None,next=None):
        self.data=data
        self.prev=prev
        self.next=next
class NodeMgmt:
    def __init__(self,data):
    #data를 받아서 node를 만들고 head와 tail에 넣음
    #처음에는 head==tail
        self.head=Node(data)        
        self.tail=self.head
   #node 추가     
   def insert(self,data):
   #node가 하나도 없는 경우 
   #Node(data)를 만들어서 head와 tail에 넣어준다
       if self.head='':
           self.head=Node(data)
           self.tail=self.head
       else:    
           node=self.head
           #node.next가 None일때까지 node를 탐색한다
           while node.next:
               node=node.next
           #맨 마지막 노드에서
           new = Node(data)
           #양방향을 이어주고
           node.next=new
           new.prev=node
           #링크드리스트의 tail을 바꿔준다
           self.tail=new
#순회
    def desc(self):
        node=self.head
        while node:
            print(node.data)
            node=node.next
#앞에서 부터 검색하는 함수
    def search_from_head(self,data):
        if self.head=='':
            return False
        else:
            node=self.head
            while node:
                if node.data==data
                    return node
                else:
                    node=node.next
#끝 노드 까지 갔는데, 해당 data를 가진 노드가 없으면 false 리턴        
            return False        
#뒤에서 부터 검색하는 함수
    def search_from_tail(self,data):
        if self.tail=='':
            return False
        else:
            node=self.tail
            while node:
                if node.data==data
                    return node
                else:
                    node=node.prev
#첫 노드 까지 갔는데, 해당 data를 가진 노드가 없으면 false 리턴 
             return False
#특정 데이터를 가진 노드 앞에 새로운 데이터를 가진 노드 삽입하기 (뒤에서 부터 탐색하기)
    def insert_from_tail(self,new_data,before_data):
    #더블 링크드리스트가 생성되지 않았을 때
        if self.head==None:
            self.head=Node(data)
            self.tail=self.head
            return True
        else:
            node=self.tail
	    #node.data가 before_data일때까지 노드를 앞으로 순회함
            while node.data!=before_data:
                node=node.prev
#만약 node==None이면, before_data를 가진 노드는 없다는 뜻이므로, False를 리턴
                if node==None:
                    return False
           #node.data 가 before_data일 때
           new = Node(new_data)
           bofore_new=node.prev
           new.prev=bofore_new
           before_new.next=new
           new.next=node
           node.prev=new
           return True
#특정 데이터를 가진 노드 뒤에 새로운 데이터를 가진 노드 삽입하기(앞에서 부터 탐색하기)  
    def insert_from_head(self,new_data,after_data):
        if self.head==None:
            self.head=Node(data)
            self.tail=self.head
            return True
        else:
            node = self.head
            while node.data!=after_data:
                node=node.next
                if noee.next==None:
                    return False
            #node.data가 after_data 일 때
            new = Node(new_data)
            after_new = node.next
            new.prev=node
            new.next=after_new
            node.next=new
            after_new.prev=new
            if new.next==None:
                self.tail=new
            return True