자바 단 방향 링크 의 기본 기능 에 대한 상세 한 설명 실현
최근 에 데이터 구조 와 알고리즘 을 돌 이 켜 보면 일부 알고리즘 문 제 는 스 택 의 사상 을 사 용 했 고 스 택 하면 링크 를 말 할 수 밖 에 없 었 다.배열 과 링크 는 모두 선형 저장 구조의 기초 이 고 스 택 과 대기 열 은 모두 선형 저장 구조의 응용 입 니 다~
본 고 는 주로 단일 체인 표 의 기초 지식 점 을 설명 하고 간단 한 입문 을 합 니 다~잘못된 부분 이 있 으 면 지적 해 주 십시오.
2.회고 와 지신
링크 하면 우리 먼저 배열 을 들 어 봅 시다.배열 과 비교 하면 링크 와 같은 저장 구 조 를 잘 이해 할 수 있 습 니 다.
2.1 회고 배열
배열 우 리 는 C,자바 든 모두 배 웠 다.
배열 의 장점:
배열 을 보고 우리 의 링크 로 돌아 갑 니 다.
n 개의 노드 가 분 산 된 분 배 는 서로 지침 을 통 해 연결 되 고 모든 노드 는 하나의 전구 노드 만 있 으 며 모든 노드 는 하나의 후속 노드 만 있 고 첫 번 째 노드 는 전구 노드 가 없 으 며 꼬리 노드 는 후속 노드 가 없다.
링크 장점:
체인 시 계 를 확인 하려 면 헤드 포인터 만 있 으 면 헤드 포인터 로 전체 체인 시 계 를 유도 할 수 있 습 니 다~
체인 시 계 는 또 여러 종류 로 나 뉘 었 다.
1.단 방향 링크
링크 를 조작 할 때 항상 기억 해 야 할 것 은:
노드 에서 포인터 영역 이 가리 키 는 것 은 하나의 노드 입 니 다!
3.자바 구현 링크
알고리즘:
public class Node {
//
public int data;
// ,
public Node next;
public Node() {
}
public Node(int data) {
this.data = data;
}
public Node(int data, Node next) {
this.data = data;
this.next = next;
}
}
3.1 링크 만 들 기(노드 증가)링크 에 데이터 삽입:
/**
*
*
* @param value
*/
public static void addData(int value) {
//
Node newNode = new Node(value);
//
Node temp = head;
//
while (temp.next != null) {
temp = temp.next;
}
// .next null ~
temp.next = newNode;
}
3.2 링크 옮 겨 다 니 기위 에 우리 가 추가 방법 을 만 들 었 으 니 이 제 는 제대로 되 었 는 지 살 펴 보 자~~
첫 번 째 노드 부터 뒤쪽 노드 에 데이터 가 없 을 때 까지 계속 찾 습 니 다.
/**
*
*
* @param head
*/
public static void traverse(Node head) {
// ,
Node temp = head.next;
while (temp != null) {
System.out.println(" Java3y:" + temp.data);
//
temp = temp.next;
}
}
결과:3.3 삽입 노드
/**
*
*
* @param head
* @param index
* @param value
*/
public static void insertNode(Node head, int index, int value) {
// ,
if (index < 1 || index > linkListLength(head) + 1) {
System.out.println(" 。");
return;
}
// ,
Node temp = head;
//
int currentPos = 0;
//
Node insertNode = new Node(value);
while (temp.next != null) {
//
if ((index - 1) == currentPos) {
//temp
//
insertNode.next = temp.next;
//
temp.next = insertNode;
return;
}
currentPos++;
temp = temp.next;
}
}
3.4 링크 의 길 이 를 가 져 옵 니 다.링크 의 길 이 를 가 져 오 는 것 은 간단 합 니 다.한 노드+1 을 얻 을 때마다~
/**
*
* @param head
*/
public static int linkListLength(Node head) {
int length = 0;
// ,
Node temp = head.next;
//
while (temp != null) {
length++;
temp = temp.next;
}
return length;
}
3.5 노드 삭제특정한 위치 에 있 는 노드 를 삭제 하 는 것 은 삽입 노드 와 비슷 하고 똑 같이 이전 노드 를 찾 아야 합 니 다.이전 노드 의 포인터 영역 을 바 꾸 면 삭제 할 수 있 습 니 다~
/**
*
*
* @param head
* @param index
*/
public static void deleteNode(Node head, int index) {
// ,
if (index < 1 || index > linkListLength(head) + 1) {
System.out.println(" 。");
return;
}
// ,
Node temp = head;
//
int currentPos = 0;
while (temp.next != null) {
//
if ((index - 1) == currentPos) {
//temp
//temp.next
//
Node deleteNode = temp.next;
//
temp.next = deleteNode.next;
//Java , null ( , ~)
deleteNode = null;
return;
}
currentPos++;
temp = temp.next;
}
}
3.6 링크 정렬앞에서 이미 8 가지 정렬 알고리즘 을 말 했 습 니 다[8 가지 정렬 알고리즘 총화].이번 에는 간단하게 거품 을 일 으 켜 정렬 합 시다.
/**
*
*
* @param head
*
*/
public static void sortLinkList(Node head) {
Node currentNode;
Node 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 번 째 노드 를 찾 습 니 다.이 알고리즘 은 매우 재 미 있 습 니 다.두 개의 포인터 p1,p2 를 설정 하여 p2 가 p1 보다 k 개의 노드 를 빠르게 하 는 동시에 뒤로 옮 겨 다 닙 니 다.p2 가 비어 있 으 면 p1 은 꼴찌 k 개의 노드 입 니 다.
/**
* k ( p1、p2, p2 p1 k , , p2 , p1 k
*
* @param head
* @param k k
*/
public static Node findKNode(Node head, int k) {
if (k < 1 || k > linkListLength(head))
return null;
Node p1 = head;
Node p2 = head;
// p2 p1 k
for (int i = 0; i < k - 1; i++)
p2 = p2.next;
// p2 null, p1 k
while (p2.next != null) {
p2 = p2.next;
p1 = p1.next;
}
return p1;
}
3.8 링크 중복 데이터 삭제거품 과 정렬 차이 가 많 지 않 아,그것 만 같 으 면 지 울 수 있어~
/**
* ( , )
*
* @param head
*/
public static void deleteDuplecate(Node head) {
// ,( --> )
Node temp = head.next;
// ( )
Node 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 조회 링크 의 중간 노드이 알고리즘 도 매우 재 미 있 습 니 다.하 나 는 매번 한 걸음 씩 걷 고 하 나 는 두 걸음 씩 걷 고 두 걸음 으로 옮 겨 다 니 며 한 걸음 씩 가 는 지침 입 니 다.그것 이 바로 중간 노드 입 니 다.
/**
*
*/
public static Node searchMid(Node head) {
Node p1 = head;
Node p2 = head;
// , , null,
while (p2 != null && p2.next != null && p2.next.next != null) {
p1 = p1.next;
p2 = p2.next.next;
}
return p1;
}
3.10 재 귀 를 통 해 끝 에서 끝까지 단일 체인 표를 출력 한다.
/**
*
*
* @param head
*/
public static void printListReversely(Node head) {
if (head != null) {
printListReversely(head.next);
System.out.println(head.data);
}
}
3.11 반전 링크
/**
*
*
* @param node
*/
public static Node reverseLinkList(Node node) {
Node prev ;
if (node == null || node.next == null) {
prev = node;
} else {
Node tmp = reverseLinkList(node.next);
node.next.next = node;
node.next = null;
prev = tmp;
}
return prev;
}
반전 링크 참조:https://www.jb51.net/article/136185.htm
마지막
링크 자 체 를 이해 하 는 것 은 어렵 지 않 지만 관련 조작 을 하면 머리 가 아프다.head.next next next next next next next..............................................................
체인 시 계 를 조작 하려 면 머리 지침 만 알 면 모든 조작 을 할 수 있다.
1.링크 에 데이터 추가
이전 노드 의 가리 키 는 방향 을 삽 입 된 노드 에 맡 깁 니 다.
이전 노드 포인터 영역 은 삽입 하고 자 하 는 노드 를 가리 키 고 있 습 니 다
이전 노드 에서 뒤의 노드 를 가리 키 는 것
8.링크 중복 데이터 삭제
10.재 귀 는 끝 에서 끝까지 단일 체인 표를 출력 한다.
총결산
이상 은 이 글 의 전체 내용 입 니 다.본 논문 의 내용 이 여러분 의 학습 이나 업무 에 어느 정도 참고 학습 가치 가 있 기 를 바 랍 니 다.궁금 한 점 이 있 으 시 면 댓 글 을 남 겨 주 셔 서 저희 에 대한 지지 에 감 사 드 립 니 다.
참고 자료:
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Is Eclipse IDE dying?In 2014 the Eclipse IDE is the leading development environment for Java with a market share of approximately 65%. but ac...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.