Home [Algorithm][Python] Linked List(링크드 리스트)
Post
Cancel

[Algorithm][Python] Linked List(링크드 리스트)

Posted Nov 21, 2022
By Sungrinhan
17 min read

링크드 리스트 (Linked List)

1. Linked List 구조

  • 연결 리스트라고도 함
  • List 즉 배열은 순차적으로 연결된 공간에 데이터를 나열하는 구조
    • 배열의 크기를(연결된 공간을) 미리 확보해 놔야 한다 -> 단점

  • 링크드 리스트는 떨어진 곳에 존재하는 데이터를 화살표로 연결해서 관리하는 데이터구조

    • 노드(Node) : 데이터 저장단위(데이터값 + 포인터)로 구성
    • 포인터(pointer): 각 노드 안에서 다음이나 이전의 노드와의 연결 정보를 가지고 있는 공간
  • 일반적인 링크드 리스트 형태 (출처: wikipedia, https://en.wikipedia.org/wiki/Linked_list)

배열의 데이터와 그 다음 배열요소의 주소(포인터)를 저장하는 것.(노드)

링크드 리스트의 장점과 단점

장점단점
자료의 삽입과 삭제가 용이포인터의 사용으로 인해 저장 공간의 낭비가 있음
리스트 내에서 자료의 이동이 필요하지 않다.알고리즘이 복잡하다.
사용 후 기억장소의 재사용이 가능특정 자료의 탐색시간이 많이 소요됨
연속적인 기억 장소의 할당이 필요하지 않다. 

ArrayList 와 LinkedList 의 비교 성능은 아래 표와 같다.

 ARRAYLISTLINKEDLIST
IndexingO(1)O(n)
Insert/delete at beginningO(n)O(1)
Insert/delete at endO(1)O(n) - last element is unknown
  O(1) - last element is known
Insert/delete in middleO(n)O(1)
Wasted spave (average)O(n)O(n)

2. 간단한 링크드 리스트 예

Node 구현

1
2
3
4
5
6
7

class Node:
	# __init__ 은 클래스 내장 메소드
	# 이 클래스로 객체를 만들때마다 노드가 생성됨(data + pointer)
	# self parameter 는 __init__ 메소드에서 사용되지 않는다.
	def __init__(self, data):
		self.data = data
		self.next = None

다음과 같이 좀더 객체 지향적으로 바꿀 수 있다.

1
2
3
4

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

Node 와 Node 연결하기 (포인터 활용)

1
2
3
4

node1 = Node(1)
node2 = Node(2)
node1.next = node2
head = node1 # 어떤 리스트인지 알아야 하기 때문에, head 를 정해줘야 함.

링크드 리스트로 데이터 추가하기 (어렵게 느껴짐 처음봄)

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): # default value가 none 일뿐, 값을 지정할 수 있다.
	self.data = data
	self.next = next

def add(data): # data 를 추가하는 함수
	node = head # 링크드 리스트의 위치를 알려주는 head 를 node 에 할당
	while node.next: # node.next 가 null 인경우를 찾을때까지 while 문을 돈다.
		node = node.next # 링크드 리스트의 다음노드가  node 에 할당되고, node.next 가 null인경우를 찾을 때 까지 반복됨.
	node.next = Node(data) # null 인놈을 찾아서, 새로운 data 를 갖고있는  노드의 주소를 기존 node 에 추가함.

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

# 2~ 9까지 각 숫자를 데이터로 갖는 노드들의 집합(링크드리스트) 완성.

링크드 리스트 데이터 출력하기

1
2
3
4
5
6
7

node = head
while node.next:
	print(node.data)
	node = node.next
print (node.data)

# 1 , 2 , 3,4,5,6,7,8,9

3. 링크드 리스트의 장단점 ( 전통적인 C언어에서의 배열과 링크드 리스트)

  • 장점

    • 미리 데이터 공간을 할당하지 않아도 됨
      • 배열은 미리 데이터 공간을 할당 해야 함

  • 단점

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

4. 링크드 리스트의 복잡한 기능1 (링크드 리스트 데이터 사이에 데이터를 추가)

  • 링크드 리스트는 유지 관리에 부가적인 구현이 필요. (출처: wikipedia, https://en.wikipedia.org/wiki/Linked_list)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Node:
	def __init__(self, data, next=None) : # 파이썬 class 함수에서는 param 이 있든 없든 self 인자를 첫번 째로 넣어줘야 한다.
	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 index in range(2,10):
	add(index)

1
2
3
4
5

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

1

node3 = Node(1.5)

1
2
3
4
5
6
7
8
9
10
11

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

node_next = node.next
node.next = node3
node3.next = node_next

1
2
3
4
5
6
7

# node 링크드 리스트의 데이터를 print 하는 함수
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

5. 파이썬 객체지향 프로그래밍으로 링크드 리스트 구현하기

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

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:
				print(node.data)
				node = node.next
			node.next = Node(data)

	# 각 노드데이터를 print 하는 description 함수
	def desc(self):
		node = self.head
		while node:
			print (node.data)
			node = node.next

1
2
3

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

1
2
3
4

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

6. 링크드 리스트의 복잡한 기능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

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

테스트를 위해 1개 노드를 만들어 봄

1
2
3

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

head 가 살아있음을 확인

1
2

linkedlist1.head
# <__main__.Node at 0x1099fc6a0> 살아 있는 것

head 를 지워봄

1

linkedlist1.delete(0)

다음 코드 실행 시 아무것도 나오지 않는다는 것은 linkedlist1.head 가 정상적으로 삭제되었음을 의미

1
2
3

linkedlist1.head

# NameError : name 'linkedlist1' is not defined

다시 하나의 노드를 만들어봄

1
2
3
4

linkedlist1 = NodeMgmt(0)
linkedlist1.desc()

# 0

이번엔 여러 노드를 더 추가해봄

1
2
3
4
5

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

# 0, 1, 2, 3, 4, 5, 6, 7, 8, 9

노드 중에 한개를 삭제함 (위에서 언급한 경우의수2)

1

linkedlist1.delete(4)

특정 노드가 삭제되었음을 알 수 있음

1
2
3

linkedlist1.desc()

# 0, 1, 2, 3, 5, 6, 7, 8, 9

하나 더 삭제해 보자.

1
2
3
4

linkedlist1.delete(9)

linkedlist1.desc()
# 0, 1, 2, 3, 5, 6, 7, 8

연습1 : 위 코드에서 노드 데이터가 특정 숫자인 노드를 찾는 함수를 만들고 테스트해보기

테스트: 임의로 1~9까지 데이터를 링크드 리스트에 넣어보고, 데이터 값이 4인 노드의 데이터 값 출력해보기.

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

class Node:
	def __init__(self, data):
		self.data = data
		self.next = None
class NodeMgmgt:
	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: # 경우의 수 1: self.head 를 삭제해야 할 경우 - self.head 를 바꿔줘야 함
			temp = self.head # self.head 객체를 삭제하기 위해, 임시로 temp 에 담아서 객체를 삭제했음
			self.head = self.head.next # 만약 self.head 각체를 삭제하면, 이 코드가 실행이 안되기 때문!
			del temp
		else:
			node = self.head
			while node.next:
				if node.next.data == data:
					temp = node.next
					node.next = node.next.next
					del temp
					pass
				else:
					node = node.next

	def search_node(self, data):
		node = self.head
		while node:
			if node.data == data:
				return node
			else:
				node = node.next


1
2
3
4
5
6
7

# 테스트
node_mgmt = NodeMgmt(0)
for data in range(1, 10):
	node_mgmt.add(data)

node = node_mgmt.search_node(4)
print (node.data)

7. 다양한 링크드 리스트 구조

  • 더블 링크드 리스트(Doubly linked list) 기본 구조
    • 이중 연결 리스트라고도 함
    • 장점: 양방향으로 연결되어 있어서 노드 탐색이 양쪽으로 모두 가능 (출처: wikipedia, https://en.wikipedia.org/wiki/Linked_list)
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

class Node:
	def __init__(self, data, prev=None, next=None):
		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

1
2
3
4
5
6

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

연습 2 : 위 코드에서 노드 데이터가 특정 숫자인 노드 앞에 데이터를 추가하는 함수를 만들고, 테스트 해보기

더블 링크드 리스트의 tail 에서부터 뒤로 이동하며, 특정 숫자인 노드를 찾는 방식으로 함수 구현하기 테스트: 임의로 0 ~ 9까지 데이터를 링크드 리스트에 넣어보고, 데이터 값이 2인 노드 앞에 1.5 데이터 값을 가진 노드를 추가해보기

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, prev = None, next = None):
		slef.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

	def search_from_head(self, data):
		if self.head == None:
			return False

		node = self.head
		while node:
			if node.data == data:
				return node
			else:
				node = node.next
		return False

	def search_from_tail(self, data):
		if self.head == None:
			return False

		node = self.tail
		while node:
			if node.data == data:
				return node
			else:
				node = node.prev
		return False

	def insert_before(self, data, before_data):
		if self.head == None:
			self.head = Node(data)
			return True
		else:
			node = self.tail
			while node.data != before_data:
				node = node.prev
				if node == None:
					return False
			new = Node(data)
			before_new = node.prev
			before new.next = new
			new.prev = before_new
			new.next = node
			node.prev = new
			return True

1
2
3
4
5
6

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

1
2
3
4

node_3 = double_linked_list.search_from_tail(3)
node_3.data

# 3

1
2
3
4

double_linked_list.insert_before(1.5, 2)
double_linked_list.desc()

# 0, 1, 1.5, 2, 3, 4, 5, 6, 7, 8, 9

1
2
3
4

node_3 = double_linked_list.search_from_tail(1.5)
node_3.data

# 1.5

연습 3 : 위 코드에서 노드 데이터가 특정 숫자인 노드 뒤에 데이터를 추가하는 함수 만들고, 테스트하기

더블 링크드 리스트의 head 에서부터 다음으로 이동하며, 특정 숫자인 노드를 찾는 방식으로 함수를 구현하기 임의로 0 ~ 9 까지 데이터를 링크드 리스트에 넣어보고, 데이터값이 1인 노드 다음에 1.7 데이터 값을 가진 노드를 추가해보기

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

class Node:
	def __init__(self, data, prev=None, next=None):
		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_before(self, data, beofre_data):
		if self.head == None:
			self.head = Node(data)
			return True
		else:
			node = self.tail
			while node.data != before_data:
				node = node.prev
				if node == None:
					return False
			new = Node(data)
			before_new = node.prev
			before_new.next = new
			new.next = node
			return True

	def insert_after(self, data, after_data):
		if self.head == None:
			self.head = Node(data)
			return True
		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

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

node_mgmt = NodeMgmt(0)
for data in range(1, 10):
	node_mgmt.insert(data)

node_mgmt.desc()

# 1,2,3,4,5,6,7,8,9

node_mgmt.insert_after(1.5, 1)
node_mgmt.desc()

# 1, 1.5, 2,3,4,5,6,7,8,9

출처

https://www.nextree.co.kr/p6506/

Algorithm, Python
algorithm python linkedlist
This post is licensed under CC BY 4.0 by the author.
Contents

[Algorithm][Python] 스택

[JS][Library] JSBarcode, html2canvas, jsPdf를 사용하여 pdf 다운로드 하기