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

순차적으로 연결된 공간에 데이터를 나열하는 배열과 달리

연결 리스트는 떨어진 곳에 있는 데이터를 연결해 관리하는 자료구조

 

• 노드(Node): (데이터값, 포인터)로 구성
• 포인터(Pointer): 각 노드에서 연결된 노드(next, prev)와의 연결 정보를 가지고 있는 공간

 

출처: wikipedia, https://ko.wikipedia.org/wiki/%EC%97%B0%EA%B2%B0_%EB%A6%AC%EC%8A%A4%ED%8A%B8

 

• 장점: 미리 데이터 공간을 할당하지 않아도 된다.
• 단점: 연결을 위한 데이터 공간이 추가로 필요하기 때문에 저장공간 효율이 높지 않다.

         연결 정보를 찾는 시간이 필요하므로 접근 속도가 느리다.

         중간에 있는 데이터 삭제 시, 앞뒤 데이터 연결을 재구성해야 한다.

 

 

Python의 List에서 연결 리스트의 기능을 모두 지원한다.

Python에서 연결 리스트를 구현할 때는 보통 Class를 활용한다.

 

# 연결 리스트 구현
class Node:
	def __init__(self, data, next=None):
    	self.data = data
        self.next = next

class NodeM:
	def __init__(self, data):
    	self.head = Node(data)

	# 데이터 추가
	def add(self, data):
		if self.head == '':
        	self.head = Node(data)
		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):
        if self.head == '': # head가 없을 때
            print ("해당 값을 가진 노드가 없습니다.")
            return
        
        if self.head.data == data: # 삭제하려는 노드가 head일 때
            temp = self.head
            self.head = self.head.next # head의 next를 head로 설정하고
            del temp # head 값 삭제
        else:
            node = self.head
            while node.next:
                if node.next.data == data: # 삭제하려는 노드가 next인 경우
                    temp = node.next
                    node.next = node.next.next # next.next를 node.next로 연결
                    del temp # next는 삭제
                    return
                else:
                    node = node.next # 계속 next로 옮기며 탐색
	# 데이터 검색
	def search(self, data):
        node = self.head
        while node:
            if node.data == data:
                return node
            else:
                node = node.next

 

 

이중 연결 리스트(Doubly linked list)

next node만 연결하는 연결 리스트와 달리

데이터가 앞, 뒤 양방향으로 연결된 자료구조

 

출처: wikipedia, https://ko.wikipedia.org/wiki/%EC%97%B0%EA%B2%B0_%EB%A6%AC%EC%8A%A4%ED%8A%B8#%EC%9D%B4%EC%A4%91_%EC%97%B0%EA%B2%B0_%EB%A6%AC%EC%8A%A4%ED%8A%B8

 

• 장점: 데이터가 양방향으로 연결되어 있어, 앞, 뒤 양쪽으로 노드 탐색이 가능하다.

# 이중 연결 리스트 구현
class Node:
	def __init__(self, data, prev=None, next=None):
    self.prev = prev
    self.data = data
    self.next = next
    
Class NodeM:
	def __init__(self, data):
    	self.head = Noda(data)
        self.tail = self.head

	def insert(self, data):
    	if self.head == None:
        	self.head = Node(data)
            self.tail = self.head
        else:
        	node = self.head
            while node.next:
            	node = node.next
            new = Node(data)
            node.next = new
            new.prev = node
            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 == None:
            return False
    
        node = self.head
        while node:
            if node.data == data:
                return node
            else:
                node = node.next
        return False
    
    def search_from_tail(self, data):
        if self.head == None:
            return False
    
        node = self.tail
        while node:
            if node.data == data:
                return node
            else:
                node = node.prev
        return False