목차

    이론공부/자료구조

    연결리스트 (Linked List)

    멍토 2020. 4. 18.

    목차

      출처 : https://swexpertacademy.com/main/learn/course/subjectDetail.do?courseId=AVuPDN86AAXw5UW6&subjectId=AWOVJ1r6qfkDFAWg

       

      SW Expert Academy

      SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!...

      swexpertacademy.com

      시작하기 전에 배열의 구조에 대해 이해를 해야 연결리스트를 왜 써야 하는지 알 수 가있다.

      메모리 상에  연속된 위치에 고정된 크기를  할당을 받아 인덱스를 이용한 접근시 O(1)의 속도로 접근을 할 수 있다.

      따라서 탐색이 많은 경우는 배열을 선택하는 것은 좋은 선택이라 할 수 있다.

      그렇지만 삽입과 삭제가 자주일어나서 데이터 이동이 빈번하게 일어난다면 오버헤드가 커지게 된다.

      또한 고정된 크기이기 때문에 할당된 크기 이상을 사용하고 싶다면 다시 할당받아 데이터를 옮겨줘야 하는 불편함이 있다.


      개념

      배열의 단점을 보안하기 위해 나온 자료구조이다.

      자료의 논리적인 순서와 메모리 상의 물리적인 순서가 일치하지 않고,

      개별적으로 위치하고 있는 원소의 주소를 연결하여 하나의 전체적인 자료구조를 이룸.

      링크를 통해 원소에 접근하므로, 순차리스트에서 물리적인 순서를 맞추기 위한 작업이 필요하지 않게된다.

      배열과 다르게 고정적인 크기가 아니므로 자료구조의 크기를 동적으로 조정할 수 있어, 메모리의 효율적인 사용이 가능하다.

      연결된 주소를 따라 이동하는 순차탐색이 되므로, 평균 데이터 탐색시간이 O(N)이 된다.

       

      리스트의 종류 : 

      단순 연결리스트

      이중 연결 리스트

      동작원리

      연결리스트 (Linked List)

      Python 구현

      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
      59
      60
      61
      62
      63
      64
      65
      66
      67
      68
      69
      70
      71
      72
      73
      74
      75
      76
      77
      78
      79
      80
      81
      82
      83
      84
      85
      86
      87
      88
      89
      90
      91
      92
      93
      94
      95
      96
      97
      98
      99
      100
      101
      102
      103
      104
      105
      106
      107
      108
      109
      110
      111
      112
      113
      114
      115
      116
      117
      118
      119
      120
      121
      122
      123
      124
      125
      126
      127
      128
      129
      130
      131
      132
      133
      134
      135
      136
      137
      138
      139
      140
      141
      142
      143
      144
      145
      146
      147
      148
      149
      150
      151
      152
      153
      154
      155
      156
      157
      158
      159
      160
      161
      #연결리스트에 사용될 노드
      class Node:
          def __init__(self, item):
              self.back_link = None
              self.item = item
              self.next_link = None
       
      #연결리스트 클래스
      class Linked_List:
          #생성시 첫시작부분과 마지막부분, 길이를 가진다.
          def __init__(self):
              self.head = None
              self.length = 0
              self.rear = None
          
          #특정 인덱스의 값을 바꾼다면
          def change(self, index, item):
              back_index = self.length - index
              #앞쪽부터 접근이 가깝다면
              if back_index > index:
                  #헤드부터 접근한다.
                  temp = self.head
                  for i in range(index):
                      temp = temp.next_link
              #뒤부터 접근이 가깝다면
              else:
                  #뒤에서부터 접근한다.
                  temp = self.rear
                  for i in range(back_index-1):
                      temp = temp.back_link
              #원소의 값 바꾸기
              temp.item = item
       
          #뒤에 추가하는 함수
          def append(self, item):
              node = Node(item)
              #노드가 하나라도 있다면
              if self.length:
                  #생성한 노드 연결한다.
                  self.rear.next_link = node
                  node.back_link = self.rear
              #노드가 하나도 없다면 헤드가 노드를 가리키도록 한다.
              else:
                  self.head = node
              #길이 하나 늘려주고
              self.length += 1
              #추가한 값을 꼬리부분으로 바꾸기
              self.rear = node
          
          #노드가 있다면 제일 앞부분의 데이터를 리턴한다.
          def getFirst(self):
              if not self.length:
                  return None
              return self.head.item
          #노드가 있다면 제일 뒷부분의 데이터를 리턴한다.
          def getLast(self):
              if not self.length:
                  return None
              return self.rear.item
       
          #인덱스를 이용한 데이터 얻기
          def get(self, index):
              #길이가 없다면 None을 리턴
              if not self.length:
                  return None
              #접근하는 인덱스가 길이를 넘어가면 제일 마지막 값 리턴
              if index >= self.length:
                  return self.rear.item
              #접근한 인덱스를 길이에서 빼본다.
              back_index = self.length - index
              #앞부분과 뒷부분 어디에서 접근하는게 빠른지 판단한다.
              #앞부분에서 빠르다면
              if back_index > index:
                  temp = self.head
                  for i in range(index):
                      temp = temp.next_link
              #뒷부분에서 빠르다면
              else:
                  temp = self.rear
                  for i in range(back_index-1):
                      temp = temp.back_link
              #결과값 리턴
              return temp.item
       
          #값을 추가하는 함수
          def insert(self, index, item):
              node = Node(item)
              #노드가 없다면
              if not self.length:
                  self.head = node
                  self.rear = node
              #인덱스가 길이를 넘어가면 마지막에 추가
              elif self.length <=index:
                  self.rear.next_link = node
                  node.back_link = self.rear
                  self.rear = node
              #넣는 인덱스가 0번이라면
              elif not index:
                  #제일 앞부분에 데이터를 넣고 주소위치를 바꿔준다.
                  self.head.back_link = node
                  node.next_link = self.head
                  self.head = node
              #위의 상황이 아니라면
              else:
                  #앞과 뒤쪽중 어디서 접근하는게 빠른지 찾는다.
                  back_index = self.length - index
                  #앞부분의 접근이 빠르다면
                  if back_index > index:
                      temp = self.head
                      for i in range(index):
                          temp = temp.next_link
                  #뒷부분의 접근이 빠르다면
                  else:
                      temp = self.rear
                      for i in range(back_index-1):
                          temp = temp.back_link
                  #찾은 값을 기준으로 노드를 추가하고 주소를 변경
                  temp.back_link.next_link = node
                  node.back_link = temp.back_link
                  node.next_link = temp
                  temp.back_link = node
              self.length += 1
       
          #원소를 꺼내며 가지고 있던 값 리턴
          def pop(self,index=-1):
              value = None
              #길이가 없다면 반환할 값이 없다.
              if not self.length:
                  value = None
              #길이가 1이라면 원소가 하나이므로 head와 rear를 None으로 바꿔준다.
              elif self.length == 1:
                  value = self.head.item
                  self.head = None
                  self.rear = None
              #0번 인덱스를 꺼낸다면 헤드를 1번인덱스에 연결해줘야 한다.
              elif not index :
                  self.head = self.head.next_link
              #인덱스가 음수이거나 길이보다 크다면 제일 마지막 값을 리턴
              elif index < 0 or index >= self.length-1:
                  value = self.rear.item
                  self.rear = self.rear.back_link
                  self.rear.next_link = None
              else :
                  #앞쪽과 뒤쪽중 가까운곳 부터 찾아서 리턴
                  back_index = self.length - index
                  if back_index > index:
                      temp = self.head
                      for i in range(index):
                          temp = temp.next_link
                  else:
                      temp = self.rear
                      for i in range(back_index-1):
                          temp = temp.back_link
                  #주소 변경작업
                  value = temp.item
                  back_node = temp.back_link
                  next_node = temp.next_link
                  back_node.next_link = next_node
                  next_node.back_link = back_node
              self.length -=1
              return value

       

      git주소 : github.com/daum7766/CS-/tree/master/DataStructure/LinkedList_python

       

      사용 예제

      https://mungto.tistory.com/182

      https://mungto.tistory.com/185

      '이론공부 > 자료구조' 카테고리의 다른 글

      트리(Tree)  (0) 2020.04.19
      큐(Queue)란 무엇인가?  (0) 2020.04.03
      Stack 이란?(개념, 동작, 구현)  (0) 2020.02.20

      댓글