1. 서문
최근 데이터 구조 및 알고리즘을 검토 할 때 일부 알고리즘 문제는 스택 아이디어를 사용하고 스택과 관련하여 링크 된 목록에 대해 이야기해야합니다. 배열 및 링크 된 목록은 선형 저장 구조의 기초이며 스택 및 대기열은 선형 저장 구조의 응용 프로그램입니다 ~
이 기사는 주로 단일 연결 목록의 기본 지식 포인트를 설명하고 간단한 소개를합니다. 실수가 있으면 수정하십시오.
2. 검토 및 지식
링크 된 목록에 대해 먼저 배열을 언급합시다. 배열과 비교하면 링크 된 목록의 저장 구조를 매우 잘 이해할 수 있습니다.
2.1 배열을 검토하십시오
우리는 C와 Java의 배열을 배웠습니다.
배열의 장점 :
배열의 단점 :
2.2 링크 목록 설명
배열을 읽은 후 링크 된 목록으로 돌아갑니다.
N 노드는 포인터를 통해 차별적으로 할당되어 서로 연결됩니다. 각 노드에는 하나의 이전 노드 만 있으며 각 노드에는 하나의 후속 노드 만 있고, 첫 번째 노드에는 이전 노드가 없으며, 테일 노드에는 후속 노드가 없습니다.
링크 된 목록의 장점 :
링크 된 목록의 단점 :
위의 그림을 통해 링크 된 목록과 관련된 용어를 설명하겠습니다.
링크 된 목록을 결정하려면 헤드 포인터 만 필요하며 링크 된 전체 목록은 헤드 포인터를 통해 추론 할 수 있습니다 ~
링크 된 목록의 몇 가지 범주가 있습니다.
1. 일원 링크 테이블
2. 양방향 링크 테이블
3. 재활용 링크 목록
링크 된 목록을 작동 할 때 기억해야 할 것은 다음과 같습니다.
노드의 포인터 필드는 노드를 가리 킵니다!
3. Java 구현 링크 목록
연산:
먼저 클래스를 노드로 정의합니다
운영의 편의를 위해, 나는 그것을 대중으로 직접 정의했습니다.
공개 클래스 노드 {// 데이터 도메인 공개 int 데이터; // 다음 노드 공개 노드를 가리키는 포인터 도메인; public node () {} public node (int data) {this.data = data; } public node (int data, node next) {this.data = data; this.next = 다음; }} 3.1 링크 된 목록 생성 (노드 추가)
링크 된 목록에 데이터를 삽입하십시오.
/*** 링크 된 목록에 데이터를 추가 할** @param 값 추가 할*/public static void addData (int value) {// 추가 할 노드를 초기화하여 새 노드 = 새 노드 (value); // 임시 노드 노드 온도 = 헤드; // 테일 노드를 찾으십시오. } // 헤드 노드가 null이 포함 된 경우 ~ temp.next = newnode; } 3.2 링크 된 목록을 가로 지르고 있습니다
우리는 위의 추가 방법을 작성했으며 이제는 그것이 올바른지 확인하기 위해 그것을 거치게 될 것입니다 ~~~
첫 번째 노드에서 시작하여 후속 노드에 데이터가 없을 때까지 계속 검색하십시오.
/ *** 링크 된 목록을 가로 지르십시오** @param 헤드 헤드 노드*/ public static void Traverse (Node Head) {// 임시 노드, 첫 번째 노드 노드 temp = head.next에서 시작합니다. while (temp! = null) {system.out.println ( "공식 계정 java3y를 따르십시오 :" + temp.data); // 다음 temp = temp.next를 계속하십시오. }}결과:
3.3 노드 삽입
/*** 삽입* @param 인덱스 포지션 삽입* @param index 위치 삽입* @param 값 값 삽입*/public static void insertNode (Node Head, Int Index, int value) {// 먼저 지정된 위치가 합법적인지 (index <1 || index> index> index)인지 결정해야합니다. 불법적인."); 반품; } // 임시 노드, 시작 노드 노드에서 시작하여 임시 임시; 헤드; // Traversal int currentpos = 0의 현재 위치를 클릭하십시오. // 삽입 될 노드를 초기화하여 insertNode = 새 노드 (값); while (temp.next! = null) {// 이전 노드의 위치는 ((index -1) == currentpos) {// temp는 이전 노드에서 삽입 된 노드에서 insertnode로 이전 노드에서 원래 포인터를 가리킨다 .next = temp.next; // 이전 노드의 포인터 필드를 삽입 할 노드에 표시합니다 .next = insertNode; 반품; } currentpos ++; temp = temp.next; }} 3.4 링크 된 목록의 길이를 가져옵니다
링크 된 목록의 길이를 얻는 것은 매우 간단합니다. 트래버스를 통해 수행 할 수 있으며 각 노드마다 +1을 얻을 수 있습니다 ~
/ *** 링크 된 목록의 길이를 가져옵니다* @param 헤드 포인터*/ public static int linklistlength (노드 헤드) {int length = 0; // 임시 노드, 첫 번째 노드 노드에서 시작하여 temp = head.next; // 테일 노드를 찾으십시오. temp = temp.next; } 반환 길이; } 3.5 노드 삭제
특정 위치에서 노드를 삭제하는 것은 실제로 삽입 노드와 매우 유사하며 이전 노드도 찾아야합니다. 이전 노드의 포인터 필드를 변경하면 삭제할 수 있습니다 ~
/** * 위치에 따라 노드 삭제 * * @param 헤드 헤드 포인터 * @param index 삭제 될 위치 */public static void deletenode (Node Head, Int Index) {// 무엇보다도 지정된 위치가 합법적인지 확인해야합니다. if (index <1 || index> linkListLength (Head) + 1) 반품; } // 임시 노드, 시작 노드 노드에서 시작하여 임시 임시; 헤드; // 레코드의 현재 위치는 int currentpos = 0입니다. while (temp.next! = null) {// 이전 노드의 위치는 ((index -1) == currentpos) {// temp를 나타냅니다 // temp.next를 삭제하려는 노드를 나타냅니다. // 삭제하려는 다음 노드는 Temp.next = deletenode.next를 제어하기 위해 이전 노드로 전달됩니다. // java는 그것을 재활용 할 것이며, 그것을 null로 설정하는 것은 의미가 없습니다 (개인적으로 맞지 않으면 옳지 않다면 ~) deletenode = null; 반품; } currentpos ++; temp = temp.next; }} 3.6 링크 된 목록을 정렬하십시오
이미 8 개의 분류 알고리즘에 대해 이야기했습니다 [8 개의 분류 알고리즘 요약]. 이번에는 간단한 버블 분류를 선택할 것입니다 (실제로는 빠른 종류를 쓰고 싶지만 시도하기가 조금 어렵습니다 ...)
/ ** * 링크 된 목록을 정렬 * * @param head * */ public static void sortlinklist (Node Head) {Node currentNode; 노드 NextNode; for (currentNode = head.next; currentNode.next! = null; currentNode = currentNode.next) {for (nextNode = head.next; nextNode.next! = null; nextNode = nextNode.next) {if (nextNode.Data> nextNode.next.Data) {int temp = nextnode.data; NextNode.Data = NextNode.next.data; NextNode.next.data = temp; }}}} 3.7 링크 된 목록에서 k-last 노드를 찾으십시오
이 알고리즘은 매우 흥미 롭습니다. P2 K 노드를 P1보다 빠르게 만들고 동시에 뒤로 이동하도록 두 개의 포인터 P1 및 P2를 설정하십시오. P2가 비어 있으면 P1은 K-th Last Node입니다.
/ *** 링크 된 목록에서 마지막 노드가 될 때까지 K-th를 찾으십시오 (두 포인터 P1과 P2를 설정하고 P1보다 빠르게 P2 K를 만들고 P2가 비어있을 때 P1은 마지막 노드* @param k k-th까지 마지막 노드*/ public node findknode (node, int, int)까지 마지막 노드** @param head** @param head* @param head* @param head* @param head** @param k k입니다. LinkListlength (Head)) NULL P1 = HEAD; 반환 P1;
3.8 링크 된 목록에서 중복 데이터를 삭제합니다
그것은 거품 정렬과 비슷합니다. 동일하다면 삭제할 수 있습니다 ~
/ ** * 링크 된 목록에서 복제 데이터 삭제 (버블 링과 유사하게 삭제와 동일) * @param 헤드 헤드 노드 */ public static void deleteduplecate (노드 헤드) {// 임시 노드, (첫 번째 노드에서 시작-> 실제 데이터로 시작) 노드 temp = head.next; // 현재 노드의 다음 노드 (첫 번째 노드) 노드 NextNode = temp.next; while (temp.next! = null) {while (nextnode.next! = null) {if (nextNode.next.data == NextNode.Data) {// 다음 노드 (현재 노드가 다음 노드를 가리키는) nextNode.next = nextNode.next.next; } else {// 다음 NextNode = NextNode.next를 계속합니다. }} // 다음 라운드 비교 temp = temp.next; }} 3.9 링크 된 목록의 중간 노드를 쿼리하십시오
이 알고리즘은 매우 흥미 롭습니다. 매번 1 단계를 차지하는 포인터, 매번 2 단계를 차지한 후 한 단계를 취하는 포인터는 중간 노드입니다.
/ *** 단일 링크 목록의 중간 노드 쿼리*/ public static node searchmid (노드 헤드) {노드 p1 = 헤드; 노드 p2 = 헤드; // 1 단계와 한 걸음 단계를 한 단계 1 단계로 나갈 때까지 한 단계 1 단계를 밟습니다. 도달 한 중간 노드 (p2! = null && p2.next! = null && p2.next.next! = null) {p1 = p1.next; p2 = p2.next.next; } 반환 p1; }3.10 단일 연결 테이블을 꼬리에서 헤드로 재귀 적으로 출력합니다
/ *** 재귀 적으로 꼬리에서 헤드로 싱글 링크 목록을 출력* @param 헤드 노드*/ public static void printlistressly (node head) {if (head! = null) {printlistressely (head.next); System.out.println (head.data); }} 3.11 리버스 링크 목록
/ *** 링크 된 목록의 반전 구현** @param 노드 링크 된 목록의 헤드 노드*/ public static node reverselinklist (노드 노드) {노드 prev; if (node == null || node.next == null) {prev = node; } else {node tmp = ReverselinkList (node.next); node.next.next = 노드; node.next = null; 이전 = TMP; } return prev; } 리버스 링크 목록에 참조 : //www.vevb.com/article/136185.htm
4. 마침내
링크 된 목록 자체를 이해하는 것은 어렵지 않지만 관련 작업을 수행 할 때 두통이 발생할 수 있습니다. 다음 다음에 다음에 다음 다음에 .... (나는 여전히 알고리즘이 약합니다 ... 나는 두뇌가 충분하지 않습니다 ...) 나는 이틀 후이 작은 것을 썼습니다 ...
링크 된 목록을 작동 할 때 헤드 포인터를 알면 무엇이든 할 수 있습니다.
1. 링크 된 목록에 데이터를 추가하십시오
2. 링크 된 목록을 가로 지르십시오
3. 주어진 위치에서 노드를 링크 된 목록에 삽입
4. 링크 된 목록의 길이를 가져옵니다
5. 주어진 위치에서 노드를 삭제하십시오
6. 링크 된 목록을 정렬하십시오
7. 링크 된 목록에서 k-last 노드를 찾으십시오
8. 링크 된 목록에서 중복 데이터를 삭제합니다
9. 링크 된 목록의 중간 노드를 쿼리하십시오
10. 재귀 적으로 단일 연결 테이블을 꼬리에서 헤드로 출력합니다
11. 리버스 링크 목록
추신 : 모든 사람의 구현은 다를 것이므로 일부 작은 세부 사항은 필연적으로 변경 될 것이며 작성하는 고정 된 방법이 없으므로 해당 기능을 실현할 수 있습니다 ~
요약
위는이 기사의 전체 내용입니다. 이 기사의 내용에 모든 사람의 연구 나 작업에 대한 특정 참조 가치가 있기를 바랍니다. 궁금한 점이 있으면 의사 소통을 위해 메시지를 남길 수 있습니다. Wulin.com을 지원 해주셔서 감사합니다.
참조 :