자료구조 : 연결 리스트

박단이·2023년 10월 19일
단방향연결리스트양방향연결리스트연결리스트자료구조
0

python 자료구조

목록 보기
3/4

연결 리스트(Linked List)는 선형 배열과 비슷하지만 전혀 다른 자료 구조이다.
선형 배열은 번호가 붙혀진 칸에 원소들을 채워넣는 방식이라면, 연결 리스트는 각 원소들을 줄줄이 엮어서 관리하는 방식이다.

그렇다면 연결 리스트는 각 원소들을 어떻게 엮는다고 하는 것일까?

연결 리스트(Linked List)란?

연결 리스트는 아래의 그림처럼 앞에 원소가 뒤에 원소를 가리키고 있는 형태이다.

연결 리스트

각 원소들은 Node로 이루어져 있다. Node는 2가지 정보를 가지고 있다:

  1. Data
    • 숫자, 문자열, boolean 등 value를 뜻한다.
  2. Link(Next)
    • 앞, 뒤 데이터를 서로 이어주는 연결 고리
    • 한 방향으로만 이어줄 수 있다.
      Node에 link가 하나만 있으면 단방향, 2개가 연결되면 양방향 연결 리스트를 만들수 있다.

연결 리스트는 Link를 통해 연결되어 있기 때문에 원소의 삽입/삭제가 보다 쉽고 빠른 시간에 처리가 된다. 이런 이유로 OS 내부에서 많이 사용하고 있다.

다만, data 뿐만 아니라 link도 메모리에 저장되어 있어야 하므로 저장공간의 소요가 크다. 또한 'k번째 원소'를 찾아가는데 시간이 오래 걸린다.

아직 연결 리스트와 배열의 차이점이 명확하게 느껴지지 않는다면 정리된 표를 확인해보자.

배열(Array)연결 리스트(Linked List)
정적 자료구조동적 자료구조
미리 크기를 정해 놓음크기를 정할 필요가 없음
연속된 메모리 주소 할당 O연속된 메모리 주소 할당 X
접근, 탐색 용이추가, 삭제 용이
index 존재Node 존재

 

단방향 연결 리스트(Singly Linked List)

우선, Node의 link가 단방향으로 흐르는 경우부터 살펴보자.
단방향 연결 리스트

위의 그림에서처럼 가장 처음 Node를 head라고 설정한다. head가 없다면 다음 원소를 찾을 수 없기 때문에 꼭 기억하고 있어야 한다.

맨 끝 Node를 tail이라고 설정한다. head만 있어도 tail까지 찾아갈 수 있지만 가장 마지막 자리에 값을 삽입하거나 삭제할 때 오랜 시간이 걸릴 수 있기 때문에 tail을 기억하도록 한다.

일반적인 언어에서 index는 0부터 시작하는데 현재 1부터 써있어서 어색할 수 있다. 이 0번째 인덱스는 뒤에 나올 내용에서 유용하게 쓰일 예정이다.

연결 리스트가 가질 수 있는 연산은 :

  1. 특정 원소(k번째) 참조
  2. 리스트 순회 (list traversal)
  3. 길이 얻어내기
  4. 원소 삽입 (insert)
  5. 원소 삭제 (delete)
  6. 두 리스트 합치기 (concat)

연결 리스트는 이 6가지 연산 중에서 삽입, 삭제, 합치기에 특히 특화된 자료구조이다.

그럼 연결 리스트를 직접 구현해보도록 하자.

단방향 노드

연결 리스트를 구현하기 위해서는 먼저 노드가 필요하다.
노드는 데이터와 link를 가지고 있는 형태로 작성한다.

class Node:
	def __init__(self, item):
    	self.data = item   # data
        self.next = None   # 아직 link가 연결되어 있지 않은 단일 노드

연결 리스트 클래스

연결 리스트는 기본적으로 head와 tail을 담고 있어야 한다.
또한, 연결 리스트의 길이를 반환할 때 항상 배열을 처음부터 세는 것보다 nodeCount를 담고 있다가 반환해주는 것이 더 빠르다.

# 처음엔 비어있는 연결 리스트 생성
class LinkedList:
	def __init__(self):
    	self.nodeCount = 0
        self.head = None  # head와 tail에는 Node를 넣어줄 예정
        self.tail.None

뒤에 설명하는 연산들은 모두 이 LinkedList class에 포함되는 함수이다.

특정 원소 참조

특정 위치의 원소를 찾기 위해서 head부터 tail까지 차례로 확인한다. 배열의 길이와 원소의 위치에 따라서 시간이 걸리므로 시간 복잡도는 O(n)O(n) 이다.

def getAt(self, pos):
	# pos가 Node의 범위를 넘어선다면 None을 반환
    if pos <= 0 and pos > nodeCount:
        return None
        
    # 1번부터 pos번째까지 curr의 다음으로 넘어간다.
    i = 1
    curr = self.head
    while i < pos:
    	curr = curr.next
        i += 1
        
    return curr

리스트 순회

순회는 연결 리스트를 처음부터 끝까지 돌면서 data만 뽑아서 list에 담아 반환한다. 시간 복잡도는 O(n)O(n)이다.

def traverse(self):
    result = []
    curr = self.head
    # curr이 None일 때는 tail을 넘어갔을 때
    while curr != None:
        result.append(curr.data)
        curr = curr.next
    
    return result

길이 얻어내기

길이는 nodeCount만 반환하면 끝! 시간 복잡도는 O(1)O(1)이다.

def getLength(self):
    return self.nodeCount

원소 삽입

특정한 위치에 원소를 삽입하려고 한다.
앞의 3가지 연산은 간단하게 구현했지만 삽입부터는 link를 수정해야한다.

  1. newNode 위치의 바로 앞에 Node를 찾는다.
  2. 새로운 노드의 next를 prev의 next로 바꿔준다.
  3. prev의 next는 새로운 노드로 변경한다.
  4. 마지막으로 nodeCount에 1을 더해준다.

원소삽입과정

주의해야할 사항

  1. 맨 앞에 원소를 넣을 때
    • 맨 앞에 원소를 넣고 싶다면 head를 newNode로 업데이트 해야 한다.
    • head는 newNode의 다음에 와야 한다.
  2. 맨 뒤에 원소를 넣을 때
    • 맨 뒤에 원소를 넣을 땐 prev 노드를 찾기 위해getAt()메소드를 사용하여 탐색을 하는 것보다 바로 tail을 지정하면 시간 복잡도를 줄일 수 있다.
    • tail을 newNode로 업데이트 해야 한다.
def insertAt(self, pos, newNode):
	# pos 의 범위가 넘어가면 False
    if pos < 1 or pos > self.nodeCount + 1:
        return False

	# 첫 번째 위치에 넣고 싶을 때
    if pos == 1:
        newNode.next = self.head
        self.head = newNode
        
    else:
    	# 마지막 위치에 넣고 싶을 땐 getAt 메소드 필요없이 tail을 불러오자.
        if pos == self.nodeCount + 1:
            prev = self.tail
        else:
            prev = self.getAt(pos - 1)
        newNode.next = prev.next
        prev.next = newNode

	# 마지막 위치에 넣을 땐 tail도 조정해야 한다.
    if pos == self.nodeCount + 1:
        self.tail = newNode

	# 마지막으로 count에 1을 더해준다.
    self.nodeCount += 1
    return True

원소 삭제

특정한 위치의 원소를 삭제하면서 해당 값을 반환하는 pop 메소드를 구현하려고 한다.
원소 삽입과 마찬가지로 prev를 찾는 것으로 시작한다.

  1. prev와 curr을 찾는다.
  2. prev의 next를 curr의 next로 바꾼다.
  3. curr의 data를 반환한다.
  4. nodeCount에서 1을 빼준다.

원소 삭제 과정

주의해야할 사항

  1. 맨 앞에 원소를 빼고 싶을 때
    • 맨 앞에 원소를 빼고 싶다면 head를 head의 next로 업데이트 해야한다.
    • 만약에 1개만 있었다면, tail을 None을 만든다.
  2. 맨 뒤에 원소를 빼고 싶을 때
    • tail을 prev로 업데이트 해야 한다.
def popAt(self, pos):
	# pos가 범위를 넘어가면 error 발생
    if pos < 1 or pos > self.nodeCount:
        raise IndexError
    
    # curr 찾기
    curr = self.getAt(pos)
    # 맨 앞의 원소를 빼고 싶을 때
    if pos == 1:
        self.head = self.head.next
        
        # list가 1개만 있을 때
        if self.nodeCount == 1:
            self.tail = None
    else:
        prev = self.getAt(pos-1)
        prev.next = curr.next
        # 맨 뒤의 원소를 빼고 싶을 때
        if pos == self.nodeCount:
            self.tail = prev
    
    # count 1 감소
    self.nodeCount -= 1
    return curr.data

두 리스트 합치기

두 리스트를 연결하는 것은 앞에 삽입과 삭제를 거쳤다면 쉽게 이해될 것이다. 뒤에 link만 수정하면 되므로 시간 복잡도는 O(n)O(n)이다.

  1. L1의 tail 다음으로 L2의 head가 오도록 한다.
  2. L2의 tail이 L1의 tail이 된다.
  3. L1과 L2의 nodeCount를 더해준다.

두 리스트 합치기

주의해야할 사항

  1. 뒤에 이어붙힐 리스트가 빈 배열이라면 tail을 업데이트 하지 않아도 된다.
def concat(self, L):
    self.tail.next = L.head
    # 뒤에 이어붙힐 tail이 있을 때만 업데이트
    if L.tail:
        self.tail = L.tail
    self.nodeCount += L.nodeCount

전체 코드


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

class LinkedList:
	def __init__(self):
    	self.nodeCount = 0
        self.head = None
        self.tail.None
		
    # 특정 원소 참조
    def getAt(self, pos):
        if pos <= 0 and pos > nodeCount:
            return None
            
        i = 1
        curr = self.head
        while i < pos:
            curr = curr.next
            i += 1
            
        return curr
        
    # 리스트 순회
    def traverse(self):
        result = []
        curr = self.head
        while curr != None:
            result.append(curr.data)
            curr = curr.next
        
        return result
    
    # 길이 얻어내기
    def getLength(self):
        return self.nodeCount
        
    # 원소 삽입
    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):
        if pos < 1 or pos > self.nodeCount:
            raise IndexError
        
        curr = self.getAt(pos)
        if pos == 1:
            self.head = self.head.next
            
            if self.nodeCount == 1:
                self.tail = None
        else:
            prev = self.getAt(pos-1)
            prev.next = curr.next
            if pos == self.nodeCount:
                self.tail = prev
        
        self.nodeCount -= 1
        return curr.data
        
    # 리스트 합치기
    def concat(self, L):
        self.tail.next = L.head
        if L.tail:
            self.tail = L.tail
        self.nodeCount += L.nodeCount

연결 리스트의 최대 장점은 삽입과 삭제가 유연하다는 것이다.
why? 배열은 삽입과 삭제가 일어나면 영향을 받는 모든 원소의 위치를 옮겨주어야하지만, 연결 리스트는 링크만 조절하면 된다.


삽입/삭제 시간복잡도

원소 삽입원소 삭제
맨 앞에O(1)O(1)O(1)O(1)
중간에O(n)O(n)O(n)O(n)
맨 끝에O(1)O(1)O(n)O(n)

dummy node

지금까지 배운 구조로는 getAt() 메소드를 사용하기 때문에 조금 시간이 오래 걸린다. 이것을 보완하기 위해 새로운 메소드를 구현하고자 한다.

  1. insertAfter(prev, newNode)
  2. popAfter(prev)

특정 위치가 아니라 삽입을 하고 제거를 하기 위한 앞에 노드를 인자로 전달하여 해결하고자 한다. 이 메서드 모두 맨 앞에 삭제와 삽입을 하려고 하니 복잡한 코드가 될 것 같다. 이때 사용하는 것이 바로 우리가 지금까지 쓰지 않았던 0번째 인덱스이다.

맨 앞에 dummy node를 추가한 형태로 head는 dummy node를 가리킨다. 기존에 만들어놨던 LinkedList() 클래스에 살짝 수정이 필요하다.

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

class LinkedList:
	def __init__(self):
		self.nodeCount = 0
		self.head = Node(None)   # head에 dummy node 지정
		self.tail = None
		self.head.next = self.tail

	# 길이 얻어내기
	def getLength(self):
		return self.nodeCount

	# 리스트 순회
	def traverse(self):
		result = []
		curr = self.head
		while curr.next:   # head는 dummy이므로 next node의 유무로 반복문을 사용한다.
			curr = curr.next   # curr을 먼저 옮긴다.
			result.append(curr.data)
		return result

	# 특정 원소 추출하기
	def getAt(self, pos):
    	# pos가 0부터 가능하므로 기준이 바뀌었다.
		if pos < 0 or pos > self.nodeCount:
			return None

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

		return curr

	# 리스트 연결하기
	def concat(self, L):
		self.tail.next = L.head.next  # head는 dummy 이므로 head 다음을 가리킨다.
		if L.tail:
			self.tail = L.tail
		self.nodeCount += L.nodeCount

원소 삽입하기 (단, 이전 노드로)

이전 노드를 인자로 받아서 삽입하는 insertAfter 메소드를 만든다. insertAt메소드는 insertAfter 메소드를 활용하도록 수정할 수 있다.

기본적으로 insertAfter 메소드는 이전에 설명한 원리와 똑같다. insertAt 메소드는 pos에 따른 prev만 잘 찾아서 넘겨주면 된다.

def insertAfter(self, prev, newNode):
    newNode.next = prev.next
    if prev.next is None:
        self.tail = newNode
    prev.next = newNode
    self.nodeCount += 1
    return True


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)

원소 삭제하기 (단, 이전 노드로)

이전 노드를 인자로 받아서 삽입하는 popAfter 메소드를 만든다. popAt메소드는 popAfter 메소드를 활용하도록 수정할 수 있다.

기본적으로 popAfter 메소드는 이전에 설명한 원리와 똑같다. popAt 메소드는 pos에 따른 prev만 잘 찾아서 넘겨주면 된다.

def popAfter(self, prev):
    curr = prev.next
    if curr == None:
        return None
    if curr.next == None:
        self.tail = prev
    prev.next = curr.next
    self.nodeCount -= 1
    return curr.data


def popAt(self, pos):
    if pos < 1 or pos > self.nodeCount:
        raise IndexError
    
    prev = self.getAt(pos-1)
    return self.popAfter(prev)

전체 코드

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:
			curr = curr.next
			result.append(curr.data)
		return result


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

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

		return curr


    def insertAfter(self, prev, newNode):
        newNode.next = prev.next
        if prev.next is None:
            self.tail = newNode
        prev.next = newNode
        self.nodeCount += 1
        return True


    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

    def popAfter(self, prev):
        curr = prev.next
        if curr == None:
            return None
        if curr.next == None:
            self.tail = prev
        prev.next = curr.next
        self.nodeCount -= 1
        return curr.data


    def popAt(self, pos):
        if pos < 1 or pos > self.nodeCount:
            raise IndexError
        
        prev = self.getAt(pos-1)
        return self.popAfter(prev)

양방향 연결 리스트(doubly linked list)

양방향 연결 리스트는 앞서 언급했던 것처럼 하나의 Node에 앞뒤로 2개의 Link가 있다. 아래의 그림에서 보는 것처럼 하나는 앞으로 가는 Next와 다른 하나는 뒤로 가는 Prev이다.
양방향 연결 리스트

양방향 연결 리스트는 단방향 연결 리스트보다 메모리 사용량이 늘어나고 개발자가 조금더 신경써야 한다는 단점을 가지고 있지만 장점이 더욱 매력적이기 때문에 양방향 연결 리스트를 많이 사용한다.

양방향 연결 리스트는 데이터 원소들을 차례로 방문할 때 앞에서 뒤로만 가능했던 단방향과는 달리 뒤에서 앞으로도 갈 수 있다는 것이 큰 장점이다. 너무 당연해보이지만 OS 등에서는 리스트를 대상으로 앞/뒤로 왔다 갔다 하면서 작업해야하는 경우가 빈번히 요구되므로, 양방향 연결 리스트를 많이 사용한다.

양방향 노드

단방향과 동일하게 먼저 노드를 구현한다. link가 앞뒤로 연결되어 있기 때문에 prev, next 둘 다 만들어 준다.

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

연결 리스트 클래스

양방향 연결 리스트의 연산을 구현하기 위한 클래스를 만든다.
head와 tail은 dummy node이기 때문에 None으로 지정해준다.
또한, head는 앞(prev)으로 가는 link가 없고 tail은 뒤(next)로 가는 link가 없기 때문에 각각 처리를 해준다.

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

특정 원소 참조

기본적인 rule은 단방향과 같다. 앞에서 뒤로 넘어가면서 탐색할 때 만약에 찾고자하는 위치가 후반부에 위치하고 있다면 리스트가 길어질수록 실행시간이 오래 걸릴 것이다. 이것을 양방향 연결 리스트는 방지할 수 있다.

앞 뒤를 나누어서 진행하기 때문에 시간 복잡도는 O(n/2)O(n/2)지만, 계수는 신경쓰지 않으므로 O(n)O(n)이다.

pos가 nodeCount의 절반인 수보다 크다면 후반부에 위치하는 것이기 때문에 tail부터 시작하면서 찾는다.

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

	# pos가 후반부에 위치할 때
	if pos > self.nodeCount // 2:
		i = 0
		curr = self.tail
        while i < self.nodeCount - pos + 1:
        	curr = curr.prev
            i += 1
	# pos가 전반부에 위치할 때
    else:
    	i = 0
        curr = self.head
        while i < pos:
        	curr = curr.next
            i += 1

	return curr

리스트 순회

head와 tail 모두 dummy node이므로 next.next가 존재할 때 다음의 값으로 넘어가서 담는다. 시간 복잡도는 O(n)O(n)이다.

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

리스트 역방향 순회

양방향 연결 리스트는 뒤에서 앞으로도 탐색할 수 있기 때문에 역방향으로도 data를 담아 반환할 수 있다. 시간 복잡도는 O(n)O(n)이다.

def reverse(self):
    result = []
    
    curr = self.tail
    while curr.prev.prev:
        curr = curr.prev
        result.append(curr.data)
    
    return result

원소 삽입(이전 노드)

양방향은 노드마다 link가 2개 있기 때문에 link를 둘다 수정해주면 된다.

  1. newNode의 prev링크에 prev노드를 지정한다.
  2. newNode의 next링크에 prev.next노드를 지정한다.
  3. prev의 next링크에 newNode노드를 지정한다.
  4. prev.next의 prev링크에 newNode노드를 지정한다.
  5. nodeCount를 1 증가시킨다.
def insertAfter(self, prev, newNode):
    next = prev.next
    newNode.prev = prev
    newNode.next = next
    prev.next = newNode
    next.prev = newNode
    self.nodeCount += 1
    return True

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

    prev = self.getAt(pos - 1)
    return self.insertAfter(prev, newNode)

원소 삽입(다음 노드)

삽입해야 하는 위치의 다음 노드가 주어졌을 때 원소를 삽입할 수도 있다. 또한 insertAt메소드는 insertBefore 메소드를 사용할 수 있다.

def insertBefore(self, next, newNode):
    prev = next.prev
    newNode.next = next
    newNode.prev = prev
    next.prev = newNode
    prev.next = newNode
    self.nodeCount += 1
    return True

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

    next = self.getAt(pos + 1)
    return self.insertBefore(next, newNode)

원소 삭제(이전 노드)

양방향은 노드마다 link가 2개 있기 때문에 마찬가지로 둘다 수정해야 한다.

  1. 제공한 prev의 next링크에 있는 데이터가 삭제해야하는 데이터(curr)이다.
  2. prev의 next링크에 curr.next 노드를 지정한다.
  3. curr.next의 prev링크에 curr.prev노드를 지정한다.
  4. nodeCount를 1 감소시킨다.
def popAfter(self, prev):
    curr = prev.next
    prev.next = curr.next
    curr.next.prev = curr.prev
    self.nodeCount -= 1
    return curr.data

def popAt(self, pos):
    if pos < 0 or pos > self.nodeCount:
        raise IndexError
    
    prev = self.getAt(pos-1)
    return self.popAfter(prev)

원소 삭제(다음 노드)

삭제해야 하는 위치의 다음 노드가 주어졌을 때 원소를 삭제할 수도 있다. 

def popBefore(self, next):
    curr = next.prev
    next.prev = curr.prev
    curr.prev.next = curr.next
    self.nodeCount -= 1
    return curr.data

두 리스트 합치기

두 리스트를 합치는 method도 링크를 수정함으로써 빠르게 작성할 수 있다.

  1. 현재 리스트의 tail.prev.next는 합쳐질 L 리스트의 head.next를 가리켜야 한다(why? head, tail이 Dummy Node)
  2. L 리스트의 head.next.prev가 현재 리스트의 tail.prev를 가리켜야 한다.
  3. 현재 리스트의 tail을 L 리스트의 tail로 수정한다.
    (단, L 리스트에 값이 없다면 수정할 필요가 없다.)
  4. 현재 리스트와 L 리스트의 nodeCount를 합한다.
def concat(self, L):
    self.tail.prev.next = L.head.next
    L.head.next.prev = self.tail.prev
    
    if L.tail.prev:
        self.tail = L.tail
        
    self.nodeCount += L.nodeCount

전체 코드

class Node:

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


class DoublyLinkedList:

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

    # 길이 얻어내기
    def getLength(self):
        return self.nodeCount

    # 리스트 순회
    def traverse(self):
        result = []
        curr = self.head
        while curr.next.next:
            curr = curr.next
            result.append(curr.data)
        return result
        
    # 리스트 역방향 순회
    def reverse(self):
        result = []
        
        curr = self.tail
        while curr.prev.prev:
            curr = curr.prev
            result.append(curr.data)
        
        return result

    # 특정 원소 참조
    def getAt(self, pos):
        if pos < 0 or pos > self.nodeCount:
            return None

        if pos > self.nodeCount // 2:
            i = 0
            curr = self.tail
            while i < self.nodeCount - pos + 1:
                curr = curr.prev
                i += 1
        else:
            i = 0
            curr = self.head
            while i < pos:
                curr = curr.next
                i += 1

        return curr


    # 원소 삽입 (이전 노드)
    def insertAfter(self, prev, newNode):
        next = prev.next
        newNode.prev = prev
        newNode.next = next
        prev.next = newNode
        next.prev = newNode
        self.nodeCount += 1
        return True

    # 원소 삽입 (다음 노드)
    def insertBefore(self, next, newNode):
        prev = next.prev
        newNode.next = next
        newNode.prev = prev
        next.prev = newNode
        prev.next = newNode
        self.nodeCount += 1
        return True
        
    # 원소 삽입 (위치)
    def insertAt(self, pos, newNode):
        if pos < 1 or pos > self.nodeCount + 1:
            return False

        prev = self.getAt(pos - 1)
        return self.insertAfter(prev, newNode)
        
    # 원소 삭제 (이전 노드)
    def popAfter(self, prev):
        curr = prev.next
        prev.next = curr.next
        curr.next.prev = curr.prev
        self.nodeCount -= 1
        return curr.data

    # 원소 삭제 (다음 노드)
    def popBefore(self, next):
        curr = next.prev
        next.prev = curr.prev
        curr.prev.next = curr.next
        self.nodeCount -= 1
        return curr.data

    # 원소 삭제 (위치)
    def popAt(self, pos):
        if pos < 0 or pos > self.nodeCount:
            raise IndexError
        
        prev = self.getAt(pos-1)
        return self.popAfter(prev)

    # 리스트 합치기
    def concat(self, L):
        self.tail.prev.next = L.head.next
        L.head.next.prev = self.tail.prev
        
        if L.tail.prev:
            self.tail = L.tail
            
        self.nodeCount += L.nodeCount

이렇듯 양방향 연결 리스트를 사용하면 생각보다 코드 구현이 조금더 깔끔해지는 것을 확인할 수 있다. 양방향 연결 리스트에서 가장 중요한 것은 head와 tail에 dummy node를 지정함으로써 깔끔한 코드를 구현할 수 있다는 것이다.

선형으로 쌓아야하는 데이터를 자주 삽입 및 삭제를 하는 문제가 있다면 양방향 연결 리스트를 먼저 떠올리도록 하자.

profile
박단이
데이터 엔지니어를 꿈꾸는 주니어 입니다!
이전 포스트

자료구조 : 선형 배열

다음 포스트

자료 구조 : 스택(Stack)

0개의 댓글