[Concept] 더블 링크드 리스트 (double linked list)

이번 글에서는 더블 링크드 리스트 (이중 연결 리스트) 에 대해 적어보겠습니다.

이전 글에서 적었던 일반 링크드 리스트는 데이터를 조회할 때 head, 즉 앞에서부터 찾아가는 방식이었습니다.

 

But, 만약 데이터가 20000개가 있고, 맨 마지막 데이터를 조회하고자한다면, 20000번 조회를 해야하는거겠죠?

대신 뒤에서부터 조회한다면 어떨까요?

 

즉, 앞쪽의 데이터를 조회할 떄는 앞에서부터, 뒤쪽의 데이터를 조회할 때는 뒤에서부터 찾아나갈 수 있는 리스트가 더블 링크드 리스트 입니다.

 

이전 기본 연결 리스트의 노드에는 데이터와 next 주소만 있었다면,

더블 연결 리스트에는 prev 주소도 함께 저장됩니다.

 

이전 기본 연결 리스트에서는, self.head()만 지정했다면,

더블 연결 리스트에는 self.tail()도 지정해줄 수 있습니다.

 

 

구조

• 장점: 양방향으로 연결되어 있어서 노드 탐색이 양쪽으로 모두 가능

 

 

설명은 주석으로 달았으니 참고하시면 이해될 거에요! 위의 내용이 이해 안 됐다면 이전 글 '링크드 리스트'를 읽고오셔도 좋을 듯 해요

1

노드 생성과 맨 끝에 노드를 추가하는 코드를 적어봅시다.

# 노드 생성
class Node:
    def __init__(self, data, prev=None, next=None):
        self.data = data
        self.prev = prev  # 더블 연결리스트니까!
        self.next = next

# 노드(linked list) 관리
class NodeMgmt:
	# 처음 노드 생성 시 호출되는 생성자
    def __init__(self, data):
        self.head = Node(data)   # 클래스 Node의 생성자 호출
        self.tail = self.head    # head이자 tail
        
    # 노드 추가
    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

 

2

특정 데이터를 앞에서부터 혹은 뒤에서부터 찾는 메서드를 적어봅시다.

# 앞에서부터 찾기
	def search_from_head(self,data):
        # 방어코드
        if self.head == None:
            return False
            
        # head에서 시작
        node = self.head
        while node:
            if node.data == data:
                return node.data
            else:
                node = node.next   # 뒤로
        return False
        
# 뒤에서부터 찾기
    def search_from_tail(self,data):
        # 방어코드
        if self.head == None:
            return False
            
        # tail에서 시작
        node = self.tail
        while node:
            if node.data == data:
                return node.data
            else:
                node = node.prev   # 앞으로
        return False

 

 

3

특정 노드 앞에 추가하는 코드입니다.

    def insert_before(self, data, before_data): # before_data 앞에 만들겠다.
        if self.head == None:
            self.head = Node(data) # head가 없으면(노드가 없으면) 생성!
            return True
        else:
            node = self.tail
            while node.data != before_data: # before_data와 일치하면?
                node = node.prev
                if node == None:
                    return False
                    
            new = Node(data)		#  그앞에 새 노드 추가
            before_new = node.prev # before_data의 앞이 before_new

	# next 주소연결
            before_new.next = new
            new.next = node

	# prev 주소 연결
            new.prev = before_new
            node.prev = new
           
            return True

 

 

4

특정 노드 뒤에 추가하는 코드입니다.

    def insert_after(self, data, after_data):
        if self.head == None:
            self.head = Node(data)
            return True
        else:
            node = self.head
            while node.data != after_data: # 일치하는 데이터 찾을 때까지 뒤로
                node = node.next
                if node == None:
                    return False
                
            # 일치하는 after_data 찾으면
            new = Node(data)
            after_new = node.next  # after_data의 뒤
            
            new.prev = node
#           after_new.prev = new
            node.next = new
            new.next = after_new
            
            # after_new가 없다면 new가 tail!
            if after_new == None:
                self.tail = new
                
            return True

중간 주석은 생략해도 결과는 잘 나와서 주석처리 해주었습니다.

 

 

5

이제 직접 노드를 생성하고, insert_after(), insert_before() 를 사용해보겠습니다.

node_mgmt = NodeMgmt(0)

# 0은 이미 생성했으니 1부터 9까지 생성!
for data in range(1, 10):
    node_mgmt.insert(data)
    
# 0 1 2 3 4 5 6 7 8 9 생성

node_mgmt.insert_before(2.5, 3)
node_mgmt.desc()  # 0 1 2 2.5 3 4 5 6 7 8 9  생성

node_mgmt.insert_after(4.5, 4)
node_mgmt.desc()  # 0 1 2 2.5 3 4 4.5 5 6 7 8 9  생성

전체 코드 참고해주세요:)

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

class NodeMgmt:            
    def __init__(self, data):
        self.head = Node(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.data
            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.data
            else:
                node = node.prev
        return False
    
    def insert_before(self, data, before_data): # before_data 앞에 만들겠다.
        if self.head == None:
            self.head = Node(data) # head가 없으면 만들면되!
            return True
        else:
            node = self.tail
            while node.data != before_data: # before_data와 일치하면 그앞에 추가
                node = node.prev
                if node == None:
                    return False
            new = Node(data)
            before_new = node.prev # before_data의 앞이 before_new

            before_new.next = new
            new.next = node

            new.prev = before_new
            node.prev = new
            # before_data 앞에 추가한 것.

            return True
        

    def insert_after(self, data, after_data):
        if self.head == None:
            self.head = Node(data)
            return True
        else:
            node = self.head
            while node.data != after_data: # 일치하는 데이터 찾을 때까지 뒤로
                node = node.next
                if node == None:
                    return False
                
            # 일치하는 after_data 찾으면
            new = Node(data)
            after_new = node.next  # after_data의 뒤
            
            new.prev = node
#           after_new.prev = new
            node.next = new
            new.next = after_new
            
            # after_new가 없다면 new가 tail!
            if after_new == None:
                self.tail = new
                
            return True