소스 썸네일형 리스트형 [자료구조/java] 스택 (Stack) - 1차원 배열, 연결리스트 구현 [ 스택 (Stack) - 1차원 배열, 연결리스트를 이용한 구현] "접시를 쌓듯이 자료를 차곡차곡 쌓아 올린 형태의 구조를 말한다" 따라서 스택은 시간순서에 따라 자료가 쌓이고, 삭제할 때는 가장 마지막에 삽입된 자료가 가장 먼저 삭제되는 후입선출(LIFO, Last-In-First-Out)의 구조를 갖는다. * push 삽입 연산 (1) top = top+1; 으로 삽입 될 위치를 확보 (2) S(top) 가 overflow 가 아니라면 top의 위치에 삽입 * pop 삭제 연산 (1) return S(top); 스택이 공백이 아니라면 top의 위치에 있는 원소 반환 (2) top = top - 1; 제일 위의 원소가 삭제되어 top이 한칸 줄었음을 표시 * 스택을 구현하기 전에 설명할 것이 있다. .. 더보기 [자료구조/java] 다항식의 연결 자료구조 표현 * 다항식의 연결 자료구조 표현 - 단순 연결 리스트를 이용하여 다항식 표현하기 - 계수, 지수, 다음노드를 가리키는 참조 노드 세개로 구성 [다항식의 단순 연결 리스트 표현] 단순 연결 리스트를 이용하여 다항식을 표현 하였다. 단순 연결 리스트는 data, next 두개의 멤버변수로만 구성했지만 다항식을 표현한 단순연결리스트는 계수(coef)와 지수(expo), 다음노드를 가리키는 next 노드로 구성하였다. 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 ListNode.java package polynomial; public class ListNode { int coef; int expo.. 더보기 [자료구조/java] 이중 연결 리스트 (Doubly Linked List) * 이중 연결 리스트 (Doubly Linked List) - 양쪽 방향으로 순회할 수 있도록 연결한 리스트 원형 연결 리스트에서 현재 노드의 바로 이전 노드에 접근하려면 전체 리스트를 한바퀴 순회해야 하는 문제를 해결 [ 삽입연산 ] (1) 삽입할 노드를 가져온다. (2) 새 노드의 데이터 필드에 값을 저장한다. (3) 새 노드의 왼쪽 노드의 오른쪽 링크(rlink)를 새 노드의 오른쪽 링크(rlink)에 저장한다. (4) 그리고 왼쪽 노드의 오른쪽 링크(rlink)에 새 노드를 주소를 저장한다. (5) 새 노드의 오른쪽 노드의 왼쪽 링크(llink)를 새 노드의 왼쪽 링크(llink)에 자장한다. (6) 그리고 오른쪽 노드의 왼쪽 링크(llink)에 새 노드의 주소를 저장한다. [ 삭제연산 ] (1).. 더보기 [자료구조/java] 원형 연결 리스트 (Circular Linked List) * 원형 연결 리스트 (Circular Linked List) - 단순 연결 리스트에서 마지막 노드가 리스트의 첫 번째 노드를 가리키게 하여 리스트의 구조를 원형으로 만든 리스트 단순 연결 리스트는 현재노드에서 이전 노드를 접근 하려면 현재 위치에 상관없이 항상 리스트의 첫번째 노드부터 시작그러나, 원형 연결 리스트는 마지막 노드와 첫번째 노드가 연결되어 링크를 따라 순회하면 이전 노드에 접근 가능* 원형 연결 리스트는 마지막에 노드를 삽입하는 것이 곧 리스트의 첫 번째에 노드를 삽입하는 것과 같은 의미를 가짐 [ 삽입연산 ] if 리스트가 비어있는 경우 (CL==null)삽입하는 노드가 리스트의 첫번째 노드이자 마지막노드1. 리스트에 새로운 노드를 추가하고, 첫번째 노드로 지정2. 새 노드의 next가.. 더보기 [자료구조/java] 단순 연결 리스트 (Linked List) * 단순 연결 리스트 (Linked List) - 노드가 하나의 링크 필드에 의해서 다음 노드와 연결되는 구조를 가진 연결 리스트 * 장점 : 삽입, 삭제가 빠르다.하지만 중간에 있는 노드를 삭제하는 경우 탐색에 소요되는 시간이 있기 때문에맨 앞에 있는 요소를 삽입, 삭제하는 경우 O(1), 중간요소를 삽입, 삭제하는 경우 O(n)의 시간복잡도를 가진다.* 단점 : 탐색이 느리다.탐색의 경우 배열이 index를 이용하기 때문에 더빠르다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344Test.java package LinkedList; public class Test { public static void mai.. 더보기 이전 1 2 3 다음
