목록연결리스트 (19)
넘치게 채우기
https://leetcode.com/problems/remove-nth-node-from-end-of-list/description/ Remove Nth Node From End of List - LeetCode Can you solve this real interview question? Remove Nth Node From End of List - Given the head of a linked list, remove the nth node from the end of the list and return its head. Example 1: [https://assets.leetcode.com/uploads/2020/10/03/remove_ex1.jpg] leetcode.com Leetcode - R..
https://leetcode.com/problems/linked-list-cycle/description/ Linked List Cycle - LeetCode Can you solve this real interview question? Linked List Cycle - Given head, the head of a linked list, determine if the linked list has a cycle in it. There is a cycle in a linked list if there is some node in the list that can be reached again by continuo leetcode.com 문제 유형 : 연결 리스트, 투 포인터 문제 난이도 : Easy 문제..
https://leetcode.com/problems/partition-list/description/ Partition List - LeetCode Can you solve this real interview question? Partition List - Given the head of a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x. You should preserve the original relative order of the no leetcode.com 문제 유형 : 연결 리스트 문제 난이도 : Medium 문제 Given the ..
https://leetcode.com/problems/maximum-twin-sum-of-a-linked-list/ Maximum Twin Sum of a Linked List - LeetCode Can you solve this real interview question? Maximum Twin Sum of a Linked List - In a linked list of size n, where n is even, the ith node (0-indexed) of the linked list is known as the twin of the (n-1-i)th node, if 0
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/KwMpE/btsf4dDas4c/dLNtK13Aem93m8HzlXhzZK/img.png)
https://leetcode.com/problems/swap-nodes-in-pairs/description/ Swap Nodes in Pairs - LeetCode Can you solve this real interview question? Swap Nodes in Pairs - Given a linked list, swap every two adjacent nodes and return its head. You must solve the problem without modifying the values in the list's nodes (i.e., only nodes themselves may be chan leetcode.com 문제 유형 : 연결 리스트 문제 난이도 : Medium 문제 Gi..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/ea9o8d/btsfe8DBoCj/XN5wsYwPAImJZrI4t5Mbz1/img.png)
https://leetcode.com/problems/swapping-nodes-in-a-linked-list/description/ Swapping Nodes in a Linked List - LeetCode Can you solve this real interview question? Swapping Nodes in a Linked List - You are given the head of a linked list, and an integer k. Return the head of the linked list after swapping the values of the kth node from the beginning and the kth node from t leetcode.com 문제 유형 : 연결..
연결 리스트(Python) - 전체 class Node(): #노드 선언 def __init__(self, data, next = None): self.data = data self.next = next class SimplyLinkedList(): def __init__(self): self.head = None def link(self, node, next): #노드 연결 node.next = next def getTail(self): #꼬리 노드 불러오기 currentNode = self.head while currentNode.next: currentNode = currentNode.next return currentNode def getIndex(self, data): #data의 인덱스 반환 ..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/lweAy/btrLyXReOrl/1kKKwh0ZqsrVGcokOsJknk/img.png)
이중 연결 리스트 이중 연결 리스트는 기존의 연결리스트와는 달리, 쌍방향으로 연결이 되어있다. 이미 한 노드를 지나쳐도, 돌아갈 수 있다. 장점 찾아야 하는 값이 tail쪽에 가까울 때, head부터 시작해서 탐색하는 번거로움 등을 없앨 수 있다. 위치를 모르는 상태에서 값을 찾을 때에도, 앞에서 절반, 뒤 끝에서 절반씩 탐색하면 훨씬 효율적이다. 단점 변수를 3개 사용한다.(이전 메모리주소, 내 엘리먼트, 다음 메모리주소) 이 과정에서 메모리를 더 사용하게된다. 구현이 복잡해진다. 그러나, 이런 단점들을 두고도, 얻게 되는 것이 많아서, 실제 연결리스트를 사용할 때, 이중 연결리스트를 많이 사용한다. 노드의 추가 노드 a↔b↔d에서 b↔d 사이에 c를 연결하고 싶으면, c의 다음 노드로 d를 연결해주고..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/LuATl/btrLj8Md6TM/WrIgttQv8JNEbQzB1THxRk/img.png)
연결 리스트는 순차 리스트와는 다르게, 리스트의 노드(요소)값의 메모리주소가 순차적이지 않다. 대신, 노드에 자신의 값과, 다음 노드의 메모리주소를 저장한다. 시작하는 노드를 머리(head)라고 하고, 맨 끝을 꼬리(tail)이라고 한다. 노드에서 다음 노드로 향하는 주소값을 포인터((Pointer)라고 한다. tail노드에서 가지고 있는 포인터값은 none 또는 null이라 한다. 접근 [2]에 있는 값을 보려면, 머리부터 다음 노드를 하나하나 찾아가야한다.(순차적으로 탐색해야한다) 시간복잡도는 O(N)이다. 삽입 A - B - C로 연결되어있는 연결 리스트 중 B-C 사이에 D 노드를 삽입하고 싶으면, B의 포인터를 D의 메모리주소, D의 포인터를 C의 메모리주소로 바꿔주면된다. 이때, 바꾸는 것의 ..