연결리스트 - 주어진 리스트가 순환이 있는지 확인하는 문제

카테고리 Python, DataStructure, LinkedList

1. 연결리스트 길이로 풀기

1
2
3
4
5
6
def isCircleLinkedlist(Linked_list):
    node = Linked_list.head
    for _ in range(len(Linked_list)):
        node = node.next

    return True if node else False
  • 연결리스트의 길이를 구하여 연결리스트의 마지막 노드의 next 를 확인한다.
    • 만약 마지막 노드의 next가 있다면, 순환연결리스트
    • 그렇지 않으면 연결리스트이다.

2. 집합을 사용하여 풀기

1
2
3
4
5
6
7
8
9
10
def isCircleLinkedlist(Linked_list):
	s = set()
	node = Linked_list.head
	while node:
		if node in s:
			return True

		s.add(node)
		node = node.next
	return False
  • 노드의 값이 중복되지 않는다면, 지나간 노드를 집합(set)에 저장한다.
  • 노드가 이동할 때 마다 집합에 있는 노드인지 확인한다.
    • 집합에 지나간 노드가 있으면 True
    • 그렇지 않으면 False

3. 중복된 값이 있을 경우, 두개의 포인트를 사용하여 풀기

1
2
3
4
5
6
7
8
9
def isCircleLinkedlist(Linked_list):
    node1 = node2 = Linked_list.head
    while node1 and node1.next:
        node1 = node1.next.next
        node2 = node2.next

        if node1 == node2:
            return True
    return False
  • node1은 두칸씩 이동한다.
  • node2는 한칸씩 이동한다.
  • 만약 순환이 있다면 언젠가는 두 노드가 만난다.
  • 순환이 없다면 node1 또는 node1.next가 None에 도달한다.

댓글 공유

연결리스트 - 클래스 구현

카테고리 Python, DataStructure, LinkedList

연결리스트 클래스

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
#파일 이름: sllist.py

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


class Linked_list:
    def __init__(self):
        self.head = None
        self.length = 0

    def __len__(self):
        return self.length

    def __str__(self):
        if self.head is None:
            return "Empty List"
        node = self.head
        string = ""
        while node.next:
            string += str(node.data) + " → "
            node = node.next
        return string + str(node.data)

    def __contains__(self, data):
        node = self.head
        while node:
            if node.data == data:
                return True
            node = node.next
        return False

    def appendleft(self, data):
        node = Node(data)
        if self.head is None:
            self.head = node
        else:
            node.next = self.head
            self.head = node
        self.length += 1

    def append(self, data):
        node = Node(data)
        if self.head is None:
            self.head = node
        else:
            prev = self.head
            while prev.next:
                prev = prev.next
            prev.next = node
        self.length += 1

    def popleft(self):
        if self.head is None:
            return None
        node = self.head
        self.head = self.head.next
        self.length -= 1
        return node.data

    def pop(self):
        if self.head is None:
            return None
        node = self.head
        if self.head.next is None:
            self.head = None
        else:
            while node.next is not None:
                prev = node
                node = node.next
            prev.next = None
        self.length -= 1
        return node.data

    def insert(self, i, data):
        if i <= 0:
            self.appendleft(data)
        elif i >= self.length:
            self.append(data)
        else:
            prev = self.head
            for _ in range(i - 1):
                prev = prev.next
            node = Node(data)
            node.next = prev.next
            prev.next = node
            self.length += 1

    def remove(self, data):
        if self.head.data == data:
            self.popleft()
            return True
        prev = self.head
        while prev.next:
            if prev.next.data == data:
                prev.next = prev.next.next
                self.length -= 1
                return True
            prev = prev.next
        return False

    def reverse(self):
        if self.length <= 1:
            return
        ahead = self.head.next
        prev = self.head
        prev.next = None
        while ahead:
            self.head = ahead
            ahead = ahead.next
            self.head.next = prev
            prev = self.head

연결리스트 테스트

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
def get_data(msg):
    print(msg, end = ">>> ")
    data = input()
    return int(data) if data.isdigit() else data

my_list = LinkedList()

while True:
    menu = """
-----------------------
실행할 명령어를 선택하세요.

[0] 연결 리스트의 상태 출력
[1] 처음에 노드 추가   [2] 끝에 노드 추가      [3] 노드 검색
[4] 첫 노드 꺼내기     [5] 마지막 노드 꺼내기  [6] 특정 위치에 노드 삽입
[7] 노드 삭제         [8] 연결 리스트 뒤집기
[9] 끝내기

"""
    print(menu, end=" >>> ")
    command = int(input())
    print("-----------------------")
    print()

    if command == 0:
        print(my_list)
    elif command == 1:
        my_list.appendLeft(get_data("추가할 값(정수, 문자)을 입력하세요."))
    elif command == 2:
        my_list.append(get_data("추가할 값(정수, 문자)을 입력하세요."))
    elif command == 3:
        data = get_data("검색할 값을 입력하세요.")
        if data in my_list:
            print(f"{data}(이)가 리스트에 있습니다.")
        else:
            print(f"{data}(이)가 리스트에 없습니다.")
    elif command == 4:
        print(my_list.popLeft())
    elif command == 5:
        print(my_list.pop())
    elif command == 6:
        index = get_data("값을 추가할 인덱스를 입력하세요.")
        my_list.insert(index, get_data("추가할 값을 입력하세요."))
    elif command == 7:
        data = get_data("삭제할 값을 입력하세요.")
        if my_list.remove(data):
            print(f"{data}(을)를 정상적으로 삭제했습니다.")
        else:
            print(f"{data}(이)가 리스트에 없습니다.")
    elif command == 8:
        my_list.reverse()
        print("리스트를 뒤집었습니다.")
    elif command == 9:
        break

댓글 공유

연결리스트 - 개념 및 설명

카테고리 Python, DataStructure, LinkedList

연결리스트

노드로 감싸진 요소를 인접한 메모리 위치가 아닌 독립적으로 저장한다.

각 노드는 next 또는 next,prev 라는 포인터로 서로 연결된 선형적인 자료구조

  • 참조: O(n)
  • 탐색: O(n)
  • 삽입 / 삭제: O(1)

연결리스트에 접근하기 위해서는 첫 노드를 가리키는 head가 반드시 있어야 한다.

노드란, data와 next로 이루어진 구조체이다. 값을 담고 있는 data, 노드와 노드를 잇는 next라는 포인터로 이루어져 있다.

싱글연결리스트

스크린샷 2023-07-15 오후 12.17.18.png

next 포인터만 존재하여 한 방향으로만 데이터가 연결된다.

원형연결리스트

마지막 노드와 첫번째 노드가 연결되어 원을 형성한다.

싱글연결리스트 또는 이중연결리스트로 이루어진 2가지 타입의 원형 리스트가 있다.

싱글연결리스트로 구성된 원형연결리스트

스크린샷 2023-07-15 오후 12.18.41.png

이중연결리스트로 구성된 원형연결리스트

스크린샷 2023-07-15 오후 12.18.50.png

랜덤접근과 순차적 접근

스크린샷 2023-07-15 오후 12.21.39.png

랜덤접근(random access, 직접접근)

  • 동일한 시간에 배열과 같은 순차적인 데이터가 있을 때, 임의의 인덱스에 해당하는 데이터에 접근할 수 있는 기능
  • vector, array는 랜덤 접근 가능하여 n번째 요소에 접근 시 O(1)

순차적 접근(squential access)

  • 데이터를 저장된 순서대로 검색하며 순차적으로 접근
  • 연결리스트, 스택, 큐는 순차적 접근만 가능하여 n번째 요소 접근 시 O(n)

📌 배열과 연결리스트 비교

배열

  • 배열은 indexing으로 원소에 접근은 쉽다. O(1)
  • 하지만 맨 끝을 제외한 위치에서 원소를 추가 / 삭제 하는 것은 연속한 메모리 공간을 확보하고 원소를 이동시켜야하므로 시간이 오래 걸린다. O(n)

연결리스트

  • 연결리스트는 이전 노드들을 순차적으로 접근해야 하므로 접근은 오래 걸린다. O(n)
  • 하지만 삽입 / 삭제는 노드를 생성하고 next, prev 포인터로 이전, 다음 노드만 연결해주면 되므로 시간 복잡도가 적다. O(1)
  • 자료의 양이 정해져 있지 않아서 추가 및 삭제하는 일이 많은 경우 연결리스트가 적합하다.

댓글 공유

  • page 1 of 1

loco9939

author.bio


author.job