[자료구조] 연결 리스트(Linked List)란?

Posted on | In
연결 리스트의 개념과 구조. 간단한 연결 리스트 노드 구현. 연결 리스트의 장단점

연결 리스트(Linked List)란?

  • 연결 리스트는 떨어진 곳에 존재하는 데이터를 화살표로 연결해서 관리하는 데이터 구조이다.
    • 배열은 순차적으로 연결된 공간에서 데이터를 나열하는 데이터 구조이다.
  • 파이썬은 리스트 타입이 연결 리스트의 기능을 모두 지원한다.

구조

  • 노드(Node): 데이터 저장 단위(데이터값, 포인터)로 구성된다.
    • 위 이미지의 경우 노드가 세개이다.
  • 포인터(Pointer): 각 노드 안에서, 다음이나 이전의 노드와의 연결 정보를 가지고 있는 공간이다.
    • 위 이미지의 경우 화살표가 시작되는 부분이 포인터이다.

간단한 연결 리스트

노드 구현

1
2
3
4
5
6
7
8
9
10
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


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

노드와 노드 연결(포인터 활용)

1
2
3
4
node1 = Node(1)
node2 = Node(2)
node1.next = node2
head = node1

데이터 추가

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Node:
    def __init__(self, data, next=None):
        self.data = data
        self.next = next


def add(data):
    node = head
    while node.next: # 노드의 넥스트가 없어질 때까지
        node = node.next
    node.next = Node(data) # 맨 끝 노드에 연결


node1 = Node(1)
head = node1
for i in range(2, 10):
    add(i)

데이터 출력

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
node = head
while node.next:
    print(node.data)
    node = node.next
print (node.data)
'''
1
2
3
4
5
6
7
8
9
'''

장단점

장점

  • 미리 데이터 공간을 미리 할당하지 않아도 된다.
    • 배열은 미리 데이터 공간을 할당해야한다.

단점

  • 연결을 위한 별도 데이터 공간이 필요하므로, 저장 공간 효율이 높지는 않다.
  • 연결 정보를 찾는 시간이 필요하므로 접근 속도가 느리다.
  • 중간 데이터 삭제 시, 앞 뒤 데이터의 연결을 재구성해야하는 부가적인 작업이 필요하다.

복잡한 기능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
node3 = Node(1.5)


node = head
search = True

while search:
    if node.data == 1:
        search = False
    else:
        node = node.next

next_node = node.next
node.next = node3
node3.next = next_node


node = head
while node.next:
    print(node.data)
    node = node.next
print (node.data)
'''
1
1.5
2
3
4
5
6
7
8
9
'''

OOP로 구현

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
class Node:
    def __init__(self, data, next=None):
        self.data = data
        self.next = next # 주소
    
class NodeMgmt: # 노드 관리
    def __init__(self, data):
        self.head = Node(data) # 맨 앞 주소를 알아야 한다.
        
    def add(self, data): # 맨 끝에 추가
        if self.head == '': # 방어 코드
            self.head = Node(data)
        else:
            node = self.head
            while node.next:
                node = node.next
            node.next = Node(data)
        
    def desc(self): # 순회
        node = self.head
        while node:
            print (node.data)
            node = node.next


linkedlist1 = NodeMgmt(0)
linkedlist1.desc()
'''
0
'''


for data in range(1, 10):
    linkedlist1.add(data)
linkedlist1.desc()
'''
0
1
2
3
4
5
6
7
8
9
'''

복잡한 기능2(노드 삭제)

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
class Node:
    def __init__(self, data, next=None):
        self.data = data
        self.next = next
    
class NodeMgmt:
    def __init__(self, data):
        self.head = Node(data)
        
    def add(self, data):
        if self.head == '':
            self.head = Node(data)
        else:
            node = self.head
            while node.next:
                node = node.next
            node.next = Node(data)
        
    def desc(self):
        node = self.head
        while node:
            print (node.data)
            node = node.next
    
    def delete(self, data): # 특정 데이터를 삭제
        if self.head == '': # 방어 코드
            print("해당 값을 가진 노드가 없습니다.")
            return
        
        if self.head.data == data: # 헤드 삭제
            temp = self.head
            self.head = self.head.next # 헤드 다음을 헤드로 설정
            del temp
        else:
            node = self.head
            while node.next:
                if node.next.data == data: # 노드의 넥스트가 삭제할 데이터라면
                    temp = node.next
                    node.next = node.next.next
                    del temp
                    return
                else:
                    node = node.next


linkedlist1 = NodeMgmt(0)
linkedlist1.desc()


linkedlist1.delete(0)


for data in range(1, 10):
    linkedlist1.add(data)


linkedlist1.delete(4)


linkedlist1.desc()
'''
0
1
2
3
5
6
7
8
9
'''

다양한 연결 리스트

이중 연결 리스트

  • 더블 링크드 리스트라고도 하며 양방향으로 연결되어있어 노드 탐색이 양쪽으로 모두 가능하다.
    • 탐색이 느린 단점을 보완했다고 볼 수 있다.

구현

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
class Node:
    def __init__(self, data, prev=None, next=None): # 기존과 다르게 3개의 데이터를 가진 노드
        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


double_linked_list = NodeMgmt(0)
for data in range(1, 10):
    double_linked_list.insert(data)
double_linked_list.desc()
'''
0
1
2
3
4
5
6
7
8
9
'''

중간에 삽입하는 함수 생성해보기.

0%