이론공부/자료구조

연결리스트 (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)이 된다.

리스트의 종류 :

단순 연결리스트

이중 연결 리스트

동작원리

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