Post

[자료구조] 5.연결 리스트-1 (Linked Lists)

Posted
By Jihyun,Ryu 17 min read

추상적 자료 구조 (ADT)

  • 추상적 자료 구조(Abstract Data Type, ADT)는 숫자형, 문자열, 리스트, 튜플, 셋, 딕셔너리 등의 자료 구조와 해당 자료 구조에서 일어날 수 있는 삽입, 삭제, 순회, 정렬, 탐색 등의 연산들의 집합을 정의한 것이다.
  • 즉, 자료가 어떤 형태의 데이터 타입으로 저장되며, 해당 데이터에 필요한 작업은 어떤 것인지 정의만 하는 것이 추상적 자료 구조이다.


연결 리스트 (Linked Lists)

  • 연결 리스트(Linked List)는 데이터 원소들을 순서 지어 늘어놓는다는 점에 있어서는 선형 배열(Linear Array)과 비슷한 면이 있다. 하지만, 데이터 원소들을 늘어놓는 방식에 있어서 두 방법은 차이가 있다.
    • 선형 배열에 속하는 Python의 리스트(List)의 경우 실제 메모리 공간에 모든 원소를 연속적으로 번호가 붙여진 칸에 원소들을 채워넣는 방식이다.
    • 이와 달리, 연결 리스트의 경우에는 각 데이터 원소는 다음 원소를 가리키는 포인터(Pointer)를 사용하여 데이터 원소의 순서를 정해 각 원소들을 줄줄이(?) 엮어 관리하는 방식이다.

  • 선형 배열처럼 원소의 인덱스를 밀고 당기는 작업이 필요한 반면, 포인터를 가지고 있는 연결 리스트는 삽입과 삭제가 유연하다. 왜냐하면, 선형 배열에서의 작업과 동일한 작업 수행 시 데이터 원소의 포인터만 변경하면 되기 때문에 더 효율적이다.

  • 하지만, 원소를 탐색하는데 있어서, 인덱스 번호만 특정해주면 되는 선형 배열 \(O(1)\) 과 달리,
    원소를 탐색하기 위해서는 첫번째 Node의 데이터 원소부터 선형 탐색 \(O(n)\) 을 수행할 필요가 있다는 단점이 있다.


  • 연결리스트 클래스를 다음과 같이 정의하여 해당 포스팅을 진행한다.

    1
2
3
4
5

      class LinkedList:
      def __init__(self, node_count, head_N=None, tail_N=None):
          self.nodeCount = node_count # 연결리스트 노드 수
          self.head = head_N # 연결리스트의 Head노드 클래스 객체
          self.tail = tail_N # 연결리스트의 Tail노드 클래스 객체


연결 리스트의 구성요소

  • 연결리스트는 데이터 원소와 포인터로 구성된 여러 개의 노드(Node)로 구성되어 있다.
    • 이때, 포인터는 순차적 노드 탐색을 수행하기 위해 다른 노드의 주소를 저장하고 있다.

  • Node 중 가장 앞에 위치한 노드를 헤드노드(Head Node), 가장 마지막에 위치한 노드를 테일 노드(Tail Node)라고 칭한다.


  • 노드 클래스는 다음과 같이 구현한다.

    1
2
3
4

      class Node:
      def __init__(self, item, next=None):
          self.data = item # 노드가 담고 있는 데이터 원소
          self.next = next # 다음 노드에 대한 정보를 담고 있는 포인터


연결리스트 핵심 연산

(1) N번째 특정 원소 탐색

  • 연결리스트에서 특정 원소를 탐색하기 위해서는 Head노드부터 순차적으로 나아가야한다.
    Head노드의 순서를 1로 명시했을 때, 연결리스트 안의 노드 탐색을 위한 코드는 다음과 같다.

    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

      class Node:
      def __init__(self, item, next=None):
          self.data = item # 노드가 담고 있는 데이터 원소
          self.next = next # 다음 노드에 대한 정보를 담고 있는 포인터
    
  class LinkedList:
      def __init__(self, node_count, head_N=None, tail_N=None):
          self.nodeCount = node_count
          self.head = head_N
          self.tail = tail_N
    
      def getAt(self, pos):
          """
          노드 탐색용 함수
          - pos: 탐색하고자하는 노드의 순서
          """
    	
          # 탐색하고자하는 Node가 연결리스트내에 위치하는가?
          if pos < 1 or pos > self.nodeCount:
              return None
    
          # Head노드의 순서를 1로 초기화한다.
          i = 1
            
          # Head노드부터 시작하여 pos에 위치한 노드를 탐색한다.
          curr = self.head
          while i < pos:
              curr = curr.next
              i += 1
          return curr
    				
      def traverse(self):
          """
          연결리스트의 노드 데이터 확인용 함수
          """
          iters = self.nodeCount
          answer = []
  
          for iter in range(1,iters+1):
              curr = self.getAt(iter)
              answer.append(curr.data)
              iter+=1
      
          return answer
    
  if __name__ == '__main__':
      # 노드 객체를 생성한다.
      N1 = Node(43)
      N2 = Node(85)
      N3 = Node(62)
    
      # 노드를 연결시키고, 연결리스트 객체를 생성한다.
      N1.next = N2
      N2.next = N3
      linkdlist = LinkedList(3, N1, N2)
    
      # 생성된 연결리스트의 노드 순서대로 데이터 원소를 출력한다.
      print(linkdlist.traverse) # [43, 85, 62]


(2) 원소의 삽입 (Insertion)

  • 연결리스트에서 원소의 삽입 과정은 다음의 절차를 따른다.
    (pos: 새로 삽입하고자 하는 Node의 위치 순서)

    1. prev(pos-1번째 Node)가 포인터가 가리키고 있던 origin(기존 pos번째 노드) 주소를
      new(새로운 pos번째 노드)의 포인터에 저장한다.
    2. prev가 new를 가리키도록 포인터를 조정한다.
    3. nodeCount(# of Node)를 1 증가 킨다.


  • 위의 과정을 클래스 내 함수(insertAt)로 정의하면 다음과 같다.

    1
2
3
4
5
6
7
8
9
10
11
12

       # 위의 설명에서는 "주소"를 명시했지만, 
   # Python코드 기준 이를 "클래스 객체"라고 재명시하겠습니다.
    
   def insertAt(self, pos, newNode):
       # prev노드 클래스 객체를 불러온다.
       prev = self.get(pos-1) 
       # (1) prev노드의 포인터(next)에 저장된 origin노드의 클래스 객체를 저장한다.	
       newNode.next = prev.next  
       # (2) prev노드의 포인터가 new노드의 클래스 객체를 바라보도록 한다.
       prev.next = newNode
       # (3) nodeCount를 1증가시킨다.
       self.nodeCount += 1


  • 이때, 연결 리스트의 원소 삽입 위치에 따라서 복잡도가 상이하다.
    • 중간
      • 위에서 제시된 과정을 따르면 된다.
      • 이때 복잡도는 선형탐색 과정이 요구되기 때문에 선형시간 \(O(n)\)에 해당한다.
    • 맨 앞
      • Head의 조정만 요구되며, prev의 조정은 필요없다.
      • 즉, new노드의 포인터에 기존 Head노드의 주소를 할당해야한다.
      • 이때 복잡도는 앞 부분만 고려하면 되기에 상수시간 \(O(1)\)에 해당한다.
    • 맨 끝
      • Tail의 조정만 요구된다.
      • 즉, 기존 tail노드의 포인터에 new노드의 주소를 할당해야한다.
      • 이때 복잡도는 끝 부분만 고려하면 되기에 상수시간 \(O(1)\)에 해당한다.


  • 마지막으로, 전체적인 원소 삽입 과정을 함수(insertAt)로 표현하면 다음과 같을 것이다.

    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

        
  class Node:...
    
  class LinkedList:
      def __init__(self, node_count, head_N=None, tail_N=None):...
    
      def getAt(self, pos):...
    		
      def traverse(self):...		

      def insertAt(self, pos, newNode):
        
          # 삽입 위치가 적절한지 체크
          if pos < 1 or pos > self.nodeCount+1: 
              return False	
            
          # "맨 앞"에 new노드를 삽입할 경우
          if pos == 1:
              newNode.next = self.head
              self.head = newNode
            
          else:
        
              # "맨 끝"에 new노드를 삽입할 경우
              if pos == self.nodeCount+1:
                  prev = self.tail
                  newNode.next = prev.next # new노드의 포인터 연결
                  prev.next = newNode # prev노드의 포인터(New) 연결
                  self.tail = newNode	# tail노드에 new노드 할당
            
              # "중간"에 new노드를 삽입할 경우
              else:
                  prev = self.getAt(pos-1) 		
                  newNode.next = prev.next # new노드의 포인터 연결
                  prev.next = newNode # prev노드의 포인터(New) 연결
                        
          # nodeCount를 1증가시킨다.
          self.nodeCount += 1
          return True
    
  if __name__ == '__main__':
      # 노드 객체를 생성한다.
      N1 = Node(43)
      N2 = Node(85)
      N3 = Node(62)
      N_new = Node(99) # 정수 99를 가진 새로운 노드 생성
    
      # 노드를 연결시키고, 연결리스트 객체를 생성한다.
      N1.next = N2
      N2.next = N3
      linkdlist = LinkedList(3, N1, N2)
    
      # 생성된 연결리스트 객체에 N_new노드 추가
      linkdlist.insertAt(2, N_new)
    
      print(linkdlist.traverse()) # [43, 99, 85, 62]


(3) 원소의 삭제 (Deletion)

  • 연결리스트에서 원소의 삭제 과정은 다음의 절차를 따른다.
    (pos: 삭제하고자 하는 Node의 위치 순서)
    1. prev(pos-1번째 Node)가 포인터가 가리키던 주소를 del(삭제할 Node)의 포인터에 저장한다.
    2. nodeCount(# of Node)를 1 감소시킨다.


  • 이때, 연결 리스트의 원소 삭제되는 위치에 따라서 복잡도가 상이하다.
    • 중간
      • 위에 제시된 과정을 따르면 된다.
      • 이때 복잡도는 선형탐색 과정이 요구되기 때문에 선형시간 \(O(n)\)에 해당한다.
    • 맨 앞
      • prev는 존재하지 않기에, Head의 조정만 요구된다.
      • 이때 복잡도는 앞 부분만 삭제하면 되기에 상수시간 \(O(1)\)에 해당한다.
    • 맨 끝
      • Tail의 조정만 요구된다.
      • 하지만, 기존 Tail노드를 삭제하기위해 Tail노드를 탐색할 뿐만 아니라 prev노드 탐색도 필요하다. 왜냐하면, 원소의 “추가”와 달리 prev노드의 포인터에 None을 할당하여 Tail노드로 전환할 필요가 있기 떄문이다. 이때, 선형탐색은 Tail에서 Head방향으로 탐색이 불가하기 때문에 Head방향에서 시작하여 Tail노드로 전환할 prev노드를 선형탐색해야한다.
      • 따라서, 이때 복잡도는 선형시간 \(O(n)\)에 해당한다.


  • 마지막으로, 전체적인 원소 삭제 과정을 함수(popAt)로 표현하면 다음과 같을 것이다.

    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

      class Node:...
    
  class LinkedList:
      def __init__(self, node_count, head_N=None, tail_N=None):...
    
      def getAt(self, pos):...
    
      def traverse(self):...		

      def popAt(self, pos):
    
          if (pos < 1) or (pos > self.nodeCount):
              raise IndexError
          else:
              # 삭제할 노드의 원소 보관
              pop_value = self.getAt(pos).data
    
          # linkdlist의 노드 수가 1개일 경우
          if self.nodeCount == 1:
              self.head = None
              self.tail = None
    
          else:
              # "맨 앞"의 노드를 삭제할 경우
              if pos == 1: 
                  self.head = self.getAt(pos).next
                            
              # "맨 끝"의 노드를 삭제할 경우
              elif pos == self.nodeCount: 
                  self.tail = self.getAt(pos-1)
                  self.tail.next = None
                            
              # "중간"의 노드를 삭제할 경우
              else: 
                  self.getAt(pos-1).next = self.getAt(pos).next
                
          # nodeCount를 1감소시킨다.
          self.nodeCount -= 1
                    
          # 삭제된 노드의 원소 반환
          return pop_value
    
  if __name__ == '__main__':
      # 노드 객체를 생성한다.
      N1 = Node(43)
      N2 = Node(85)
      N3 = Node(62)
    
      # 노드를 연결시키고, 연결리스트 객체를 생성한다.
      N1.next = N2
      N2.next = N3
      linkdlist = LinkedList(3, N1, N2)
    		
      # 생성된 연결리스트 객체의 3번째 노드를 삭제한다.
      print(linkdlist.popAt(3)) # 85
      print(linkdlist.traverse()) # [43, 99, 62]


(4) 두 리스트 병합(Concatenation)

  • 독립된 연결리스트들의 병합 과정은 다음의 절차를 따른다.
    (L1: 병합 시 앞 부분에 위치한 연결리스트, L2: 병합 시 뒷 부분에 위치한 연결리스트)

    1. L1.Tail를 L2.Head노드 바라보게 하기위해서
      L1.Tail의 포인터에 L2.Head의 주소를 할당한다.
    2. 병합된 L1.Tail를 L2.Tail로 전환하는 과정을 수행한다.
      만약, 병합되는 연결리스트L2가 비어있을 경우 (즉, L2.Tail = None)
      과정을 수행하지 않는다.
    3. 기존 L1과 L2의 nodeCount를 합산해 병합된 L1.nodeCount에 할당한다.


  • 위의 과정을 클래스 내 함수(concat)로 구현하면 다음과 같다.

    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

      class Node:...
    
  class LinkedList:
      def __init__(self, node_count, head_N=None, tail_N=None):...
    
      def getAt(self, pos):...
    
      def traverse(self):...		

      def concat(self, L2):
            
          # 1. L1.Tail의 포인터에 L2.Head의 클래스 객체를 할당한다.
          self.tail.next = L2.head
            
          # 2. L2가 유효한 경우에만 L1.Tail의 위치를 L2.Tail로 변경한다. 
          if L2.tail:
              self.tail = L2.tail
        
          # 3. 병합된 연결리스트의 nodeCount를 재집계한다.
          self.nodeCount += L2.nodeCount


References

Data, Data Structure
Data Data Structure ADT Linked Lists
This post is licensed under CC BY 4.0 by the author.