배열(Array)과 리스트(List)
출처 : Linked list - Data Structure (자료구조) (opentutorials.org)
Linked List(연결 리스트)
출처 : Linked List Data Structure (programiz.com)
리스트는 순서가 있는 데이터를 늘어놓은 형태의 자료구조를 의미한다. 스택과 큐 또한 리스트 자료구조에 해당하며, 링크드 리스트는 각각의 데이터가 그 다음의 데이터를 가리키는 방식으로 순서를 구현한다.
출처 : Linked list - Data Structure (자료구조) (opentutorials.org)
각 노드가 데이터와 포인트를 가지고 한 줄로 연결되어 있으며, 노드의 포인터가 다음이나 이전의 노드와의 연결을 담당한다.
출처: [Python/파이썬] 자료구조 - 링크드리스트(Linked List) 1 (tistory.com)
Node : 데이터와 다음 데이터를 가리키는 주소(포인터)로 이루어져 있음. Element
Pointer 각 노드에서 다음 데이터를 가리키는 주소값
Head 연결 리스트에서 가장 시작점인 데이터
Tail 연결 리스트에서 가장 마지막 데이터
Next=None(or Null) 다음 데이터가 없을 경우 주속밧은 None(or Null)
연결 리스트는 늘어선 노드의 중간지점에서도 자료의 추가와 삭제가 O(1) 의 시간에 가능하다는 장점을 갖는다. 그러나 배열이나 트리 구조 와는 달리 특정 위치의 데이터를 검색해 내는데에는 O(n)의 시간이 걸리는 단점도 갖고 있다.
출처: Linked list - Data Structure (자료구조) (opentutorials.org) (생활코딩)
노드
class Node:
# Creating a node
def __init__(self, item):
self.item = item # 데이터 할당
self.next = None # 다음 노드를 Null로 초기화연결리스트 생성
# Linked list implementation in Python
class Node:
# Creating a node
def __init__(self, data):
self.data= data # 데이터 할당
self.next = None # 다음 노드를 Null로 초기화
class LinkedList:
def __init__(self, data):
self.head = Node(data)
#헤더부터 탐색해 뒤에 새로운 노드 추가하기
def append(self, data):
cur = self.head
while cur.next is not None:
cur = cur.next
cur.next = Node(data)
#모든 노드 값 출력
def print_all(self):
cur = self.head
while cur is not None:
print(cur.data)
cur = cur.next연결리스트 생성과 각 노드의 연결 예제
if __name__ == '__main__':
linked_list = LinkedList()
# Assign item values
linked_list.head = Node(1)
second = Node(2)
third = Node(3)
'''
Three nodes have been created.
We have references to these three blocks as head,
second and third
llist.head second third
| | |
| | |
+----+------+ +----+------+ +----+------+
| 1 | None | | 2 | None | | 3 | None |
+----+------+ +----+------+ +----+------+
'''
# Connect nodes
linked_list.head.next = second
'''
Now next of first Node refers to second. So they
both are linked.
llist.head second third
| | |
| | |
+----+------+ +----+------+ +----+------+
| 1 | o-------->| 2 | null | | 3 | null |
+----+------+ +----+------+ +----+------+
'''
second.next = third
'''
Now next of second Node refers to third. So all three
nodes are linked.
llist.head second third
| | |
| | |
+----+------+ +----+------+ +----+------+
| 1 | o-------->| 2 | o-------->| 3 | null |
+----+------+ +----+------+ +----+------+
'''
# Print the linked list item
while linked_list.head != None:
print(linked_list.head.item, end=" ")
linked_list.head = linked_list.head.next노드 인덱스 찾기
def get_node(self, index):
cnt = 0
node = self.head
while cnt < index:
cnt += 1
node = node.next
return node노드의 삽입
# This function is in LinkedList class
# Function to insert a new node at the beginning
def push(self, new_data):
# 1 & 2: Allocate the Node &
# Put in the data
new_node = Node(new_data)
# 3. Make next of new Node as head
new_node.next = self.head
# 4. Move the head to point to new Node
self.head = new_node연결리스트의 생성과 노드 삽입, 삭제
# A complete working Python3 program to
# demonstrate deletion in singly
# linked list with class
# Node class
class Node:
# Constructor to initialize the node object
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
# Function to initialize head
def __init__(self):
self.head = None
# Function to insert a new node at the beginning
def push(self, new_data):
new_node = Node(new_data)
new_node.next = self.head
self.head = new_node
# Given a reference to the head of a list and a key,
# delete the first occurrence of key in linked list
def deleteNode(self, key):
# Store head node
temp = self.head
# If head node itself holds the key to be deleted
if (temp is not None):
if (temp.data == key):
self.head = temp.next
temp = None
return
# Search for the key to be deleted, keep track of the
# previous node as we need to change 'prev.next'
while(temp is not None):
if temp.data == key:
break
prev = temp
temp = temp.next
# if key was not present in linked list
if(temp == None):
return
# Unlink the node from linked list
prev.next = temp.next
temp = None
# Utility function to print the linked LinkedList
def printList(self):
temp = self.head
while(temp):
print (" %d" %(temp.data)),
temp = temp.next
# Driver program
llist = LinkedList()
llist.push(7)
llist.push(1)
llist.push(3)
llist.push(2)
print ("Created Linked List: ")
llist.printList()
llist.deleteNode(1)
print ("\nLinked List after Deletion of 1:")
llist.printList()
# This code is contributed by Nikhil Kumar Singh (nickzuck_007)실행결과
Created Linked List:
2 3 1 7
Linked List after Deletion of 1:
2 3 7Reference
Linked List Data Structure - GeeksforGeeks
Linked list - Wikipedia
Linked List Data Structure (programiz.com)
[DS] 링크드 리스트 (Linked List) (hudi.blog)
[자바스크립트] 연결리스트(Linked List) 예시를 통해 쉽게 이해하기 (1) (tistory.com)
[Python/파이썬] 자료구조 - 링크드리스트(Linked List) 1 (tistory.com)
연결 리스트 - 나무위키 (namu.wiki)
