가장 기본 적 인 동적 데이터 구조: 링크
링크 는 선형 구조 이자 가장 기본 적 인 동적 데이터 구조 이다.우 리 는 동적 배열, 스 택 과 대기 열 을 실현 할 때 바 텀 은 모두 정적 배열 을 바탕 으로 resize 로 고정 용량 의 문 제 를 해결 하고 링크 는 진정한 동적 데이터 구조 이다.링크 와 같은 데이터 구 조 를 배우 면 인용 (또는 지침) 과 재 귀 를 더욱 깊이 이해 할 수 있다.그 중에서 체인 표 는 싱글 체인 표 와 더 블 체인 표 로 나 뉘 는데 본 고 에서 소개 한 것 은 싱글 체인 표 이다.
링크 의 데 이 터 는 하나의 노드 에 저 장 된 것 으로 다음 과 같은 가장 기본 적 인 노드 구조 이다.
class Node {
E e;
Node next; //
}우 리 는 체인 시 계 를 기차 라 고 상상 할 수 있다. 모든 칸 은 하나의 노드 이 고 승객 들 이 기차 칸 에 타면 요소 가 체인 테이블 의 노드 에 저장 되 는 것 과 같다.기차 의 모든 칸 은 다음 칸 과 연결 되 어 있 는데 마치 링크 의 노드 가 다음 노드 의 인용 을 가지 고 있 는 것 과 같다.기차 의 마지막 칸 은 어떤 칸 도 연결 되 지 않 았 습 니 다. 마치 링크 의 끝 부분 이 null 을 가리 키 는 것 과 같 습 니 다.
링크 의 장단 점:
/**
* @program: Data-Structure
* @description:
* @author: 01
* @create: 2018-11-08 15:37
**/
public class LinkedList {
/**
*
*/
private class Node {
E e;
Node next;
public Node() {
this(null, null);
}
public Node(E e) {
this(e, null);
}
public Node(E e, Node next) {
this.e = e;
this.next = next;
}
@Override
public String toString() {
return e.toString();
}
}
/**
*
*/
private Node head;
/**
*
*/
private int size;
public LinkedList() {
this.head = null;
this.size = 0;
}
/**
*
*
* @return
*/
public int getSize() {
return size;
}
/**
*
*
* @return true， false
*/
public boolean isEmpty() {
return size == 0;
}
} 링크 에 요 소 를 추가 합 니 다.
우리 가 배열 에 요 소 를 추가 할 때 가장 편리 한 추가 방식 은 배열 뒤에서 추가 하 는 것 입 니 다. size 는 항상 배열 의 마지막 요소 + 1 의 위 치 를 가리 키 기 때문에 size 변 수 를 이용 하여 우 리 는 요소 의 추 가 를 쉽게 완성 할 수 있 습 니 다.
반면에 링크 에서 우 리 는 체인 헤더 에 새로운 요 소 를 추가 하 는 것 이 가장 편리 합 니 다. 링크 안에 head 변 수 를 유지 하기 때 문 입 니 다. 즉, 링크 의 머리 입 니 다. 우 리 는 새로운 요 소 를 새로운 노드 에 넣 은 다음 에 새로운 노드 안의 next 변 수 를 head 에 가리 키 고 마지막 으로 head 를 이 새로운 노드 에 가리 키 면 요소 의 추 가 를 완성 합 니 다.
우 리 는 체인 헤더 에 새로운 요 소 를 추가 하 는 방법 을 실현 합 니 다. 코드 는 다음 과 같 습 니 다.
/**
* e
*
* @param e
*/
public void addFirst(E e) {
Node node = new Node(e);
node.next = head;
head = node;
// ，
//
// head = new Node(e, head);
size++;
}그 다음 에 우 리 는 링크 에서 지정 한 위치 에 새로운 노드 를 삽입 하 는 방법 을 살 펴 보 자. 비록 이것 은 링크 에서 자주 사용 하 는 조작 이 아니 지만 일부 링크 와 관련 된 문 제 는 이런 조작 과 관련 될 수 있 기 때문에 우 리 는 알 아야 한다.예 를 들 어 우 리 는 지금 '색인' 이 2 인 위치 에 새로운 노드 를 삽입 하려 고 합 니 다. 어떻게 실현 해 야 합 니까?
링크 에 진정한 색인 이 없 지만 지정 한 위치 에 새로운 노드 를 삽입 하기 위해 서 는 색인 이라는 개념 을 참조 해 야 합 니 다.위의 그림 에서 체인 표 두 를 색인 0 으로 보고 다음 노드 는 색인 1 로 본다.그 다음 에 우 리 는 prev 변수 가 필요 합 니 다. 이 변 수 를 순환 적 으로 이동 해서 지정 한 '색인' - 1 의 위 치 를 찾 아야 합 니 다. 찾 은 후에 새로운 노드 의 next 를 prev 의 next 로 가리 키 고 prev 의 next 를 새로운 노드 로 가리 키 면 이 노드 를 삽입 하 는 논 리 를 완성 할 수 있 습 니 다. 그래서 닫 는 키 점 은 추가 할 노드 의 앞 노드 를 찾 는 것 입 니 다.
구체 적 인 실현 코드 는 다음 과 같다.
/**
* index(0-based) e
*
* @param index
* @param e
*/
public void add(int index, E e) {
//
if (index < 0 || index > size) {
throw new IllegalArgumentException("Add failed. Illegal index.");
}
//
if (index == 0) {
addFirst(e);
} else {
Node prev = head;
// prev index - 1
for (int i = 0; i < index - 1; i++) {
prev = prev.next;
}
Node node = new Node(e);
node.next = prev.next;
prev.next = node;
// ，
// prev.next = new Node(e, prev.next);
size++;
}
}상기 방법 을 바탕 으로 우 리 는 링크 끝 에 새로운 요 소 를 추가 하 는 것 을 쉽게 실현 할 수 있다.
/**
* e
*
* @param e
*/
public void addLast(E e) {
add(size, e);
}링크 의 가상 헤드 노드 사용 하기
이전 소절 에서 우 리 는 지 정 된 위치 에 요 소 를 삽입 하 는 코드 를 실현 하려 면 체인 헤더 의 위 치 를 특수 하 게 처리 해 야 한다. 왜냐하면 체인 헤더 에 이전 노드 가 없 기 때문이다.체인 시 계 를 사용 하 는 경우 가 많 고 비슷 한 특수 처 리 를 해 야 하기 때문에 우아 하지 않 기 때문에 이 소절 은 이 문 제 를 우아 하 게 해결 하 는 방법 을 소개 하 는 것 이다.
특수 처 리 를 하려 는 이 유 는 head 가 이전 노드 가 없 기 때 문 입 니 다. prev 를 초기 화 할 때 head 만 가리 킬 수 있 습 니 다. 그러면 우 리 는 그 앞 에 노드 를 추가 하 는 것 이 좋 습 니 다. 이 노드 는 데 이 터 를 저장 하지 않 고 가상 노드 로 만 사용 합 니 다.이것 도 링크 구 조 를 작성 할 때 자주 사용 하 는 기술 입 니 다. 이 노드 를 추가 하면 링크 의 조작 논 리 를 통일 할 수 있 습 니 다.
수 정 된 코드 는 다음 과 같 습 니 다.
public class LinkedList {
...
/**
*
*/
private Node dummyHead;
/**
*
*/
private int size;
public LinkedList() {
this.dummyHead = new Node(null, null);
this.size = 0;
}
/**
* index(0-based) e
*
* @param index
* @param e
*/
public void add(int index, E e) {
if (index < 0 || index > size) {
throw new IllegalArgumentException("Add failed. Illegal index.");
}
Node prev = dummyHead;
// prev index
for (int i = 0; i < index; i++) {
prev = prev.next;
}
Node node = new Node(e);
node.next = prev.next;
prev.next = node;
// ，
// prev.next = new Node(e, prev.next);
size++;
}
/**
* e
*
* @param e
*/
public void addFirst(E e) {
add(0, e);
}
/**
* e
*
* @param e
*/
public void addLast(E e) {
add(size, e);
}
} 링크 의 옮 겨 다 니 기, 조회, 수정
상기 소절 의 기초 가 있 으 면 그 다음 에 우 리 는 링크 의 옮 겨 다 니 기, 조회 와 수정 을 실현 하면 매우 간단 하 다. 코드 는 다음 과 같다.
/**
* index(0-based)
*
* @param index
* @return
*/
public E get(int index) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("Get failed. Illegal index.");
}
Node cur = dummyHead.next;
for (int i = 0; i < index; i++) {
cur = cur.next;
}
return cur.e;
}
/**
*
*
* @return
*/
public E getFirst() {
return get(0);
}
/**
*
*
* @return
*/
public E getLast() {
return get(size - 1);
}
/**
* index(0-based) e
*
* @param index
* @param e
*/
public void set(int index, E e) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("Set failed. Illegal index.");
}
Node cur = dummyHead.next;
for (int i = 0; i < index; i++) {
cur = cur.next;
}
cur.e = e;
}
/**
* e
*
* @param e
* @return
*/
public boolean contain(E e) {
Node cur = dummyHead.next;
//
while (cur != null) {
if (cur.e.equals(e)) {
return true;
}
cur = cur.next;
}
return false;
}
@Override
public String toString() {
if (isEmpty()) {
return "[]";
}
StringBuilder sb = new StringBuilder();
sb.append(String.format("LinkedList: size = %d
", size));
sb.append("[");
Node cur = dummyHead.next;
//
for (int i = 0; i < size; i++) {
sb.append(cur.e).append(" -> ");
cur = cur.next;
}
//
// for (Node cur = dummyHead.next; cur != null; cur = cur.next) {
// sb.append(cur.e).append(" -> ");
// }
return sb.append("NULL]").toString();
}링크 에서 요소 삭제
마지막 으로 우리 가 실현 하고 자 하 는 링크 작업 은 바로 링크 에서 요 소 를 삭제 하 는 것 이다. 요 소 를 삭제 하면 링크 의 노드 를 삭제 하 는 것 과 같다.예 를 들 어 '색인' 이 2 인 노드 를 삭제 하려 면 같은 prev 변 수 를 사용 하여 삭제 할 노드 의 앞 노드 로 순환 이동 해 야 합 니 다. 이때 prev 의 next 를 꺼 내 면 삭제 할 노드 입 니 다. 노드 를 삭제 하 는 것 도 간단 합 니 다. 삭제 할 노드 를 꺼 낸 후에 prev 의 next 를 삭제 할 노드 의 next 를 가리 킵 니 다.
마지막 으로 삭 제 될 노드 를 null 로 가리 키 고 링크 에서 벗 어 나 게 하면 쓰레기 에 의 해 신속하게 회수 되 고 노드 의 삭 제 를 완성 할 수 있 습 니 다.
구체 적 인 실현 코드 는 다음 과 같다.
/**
* index(0-based) ，
*
* @param index
* @return
*/
public E remove(int index) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("remove failed. Illegal index.");
}
Node prev = dummyHead;
for (int i = 0; i < index; i++) {
prev = prev.next;
}
Node delNode = prev.next;
//
prev.next = delNode.next;
delNode.next = null;
size--;
return delNode.e;
}이상 의 이 방법 을 바탕 으로 우 리 는 다음 과 같은 두 가지 방법 을 간단하게 실현 할 수 있다.
/**
*
*
* @return
*/
public E removeFirst() {
return remove(0);
}
/**
*
*
* @return
*/
public E removeLast() {
return remove(size - 1);
}마지막 으로 우리 가 실현 한 이 링크 의 삭제 와 수정 작업 의 시간 복잡 도 를 살 펴 보 자.
addLast(e) // O(n)
addFirst(e) // O(1)
add(index, e) // O(n)
removeLast() // O(n)
removeFirst() // O(1)
remove(index) // O(n)
set(index, e) // O(n)
get(index) // O(n)
contain(e) // O(n)링크 로 스 택 구현
링크 의 addFirst 와 removeFirst 방법의 시간 복잡 도 를 보면 알 수 있 듯 이 링크 헤더 만 증가, 삭제 작업 의 복잡 도 는 O (1) 이 고 링크 헤더 의 요소 복잡 도 만 조회 하 는 것 도 O (1) 이다. 이때 우 리 는 링크 를 사용 하여 스 택 을 실현 하고 링크 로 이 루어 진 스 택 의 스 택 출입 스 택 등 작업 시간 복잡 도 는 모두 O (1) 라 고 생각 할 수 있다.의 구체 적 인 실현 코드 는 다음 과 같다.
/**
* @program: Data-Structure
* @description:
* @author: 01
* @create: 2018-11-08 23:38
**/
public class LinkedListStack implements Stack {
private LinkedList linkedList;
public LinkedListStack() {
this.linkedList = new LinkedList<>();
}
@Override
public int getSize() {
return linkedList.getSize();
}
@Override
public boolean isEmpty() {
return linkedList.isEmpty();
}
@Override
public void push(E e) {
linkedList.addFirst(e);
}
@Override
public E pop() {
return linkedList.removeFirst();
}
@Override
public E peek() {
return linkedList.getFirst();
}
@Override
public String toString() {
if (isEmpty()) {
return "[]";
}
StringBuilder sb = new StringBuilder();
sb.append(String.format("LinkedListStack: size = %d
", getSize()));
sb.append("top [");
for (int i = 0; i < getSize(); i++) {
sb.append(linkedList.get(i));
if (i != getSize() - 1) {
sb.append(", ");
}
}
return sb.append("]").toString();
}
//
public static void main(String[] args) {
Stack stack = new LinkedListStack<>();
for (int i = 0; i < 5; i++) {
stack.push(i);
System.out.println(stack);
}
stack.pop();
System.out.println(stack);
}
} 꼬리 포인터 가 있 는 링크: 링크 를 사용 하여 대기 열 을 실현 합 니 다.
지난 소절 에서 우 리 는 링크 를 바탕 으로 스 택 구 조 를 쉽게 실현 했다. 본 소절 에서 우 리 는 링크 를 어떻게 사용 하여 대기 열 구 조 를 실현 하 는 지 살 펴 보고 링크 에 대해 어떤 개선 을 해 야 하 는 지 살 펴 보 자.
코드 를 작성 하기 전에 우 리 는 한 가지 문 제 를 고려 해 야 합 니 다. 이전 링크 구조의 실현 코드 에는 헤드 변수 가 헤드 노드 를 가리 키 고 있 습 니 다. 만약 에 우리 가 이 링크 를 직접 사용 하여 대기 열 을 실현 하려 면 체인 끝의 요 소 를 조작 해 야 할 때 복잡 도 는 O (n) 입 니 다. 전체 링크 를 끝 노드 까지 옮 겨 다 녀 야 하기 때 문 입 니 다. 그러면 어떻게 옮 겨 다 니 는 것 을 피해 야 합 니까? O (1) 에서복잡 도 에서 꼬리 노드 를 신속하게 찾 을 수 있 습 니까? 정 답 은 tail 변 수 를 추가 하여 이 변 수 를 항상 꼬리 노드 를 가리 키 게 하면 됩 니 다. 그러면 우리 가 꼬리 노드 를 조작 하 는 복잡 도 는 O (1) 입 니 다.
그 밖 에 링크 를 사용 하여 대기 열 을 실현 하 는 데 고려 해 야 할 문제 가 있 습 니 다. 그것 은 바로 어느 쪽 에서 가입 요 소 를 만 들 고 어느 쪽 에서 팀 요 소 를 만 드 느 냐 하 는 것 입 니 다. 우리 가 전에 작성 한 링크 코드 에 체인 첫 번 째 에 요 소 를 추가 하 는 것 은 O (1) 입 니 다.네, 가장 간단 하고 편리 합 니 다. 그래서 우 리 는 체인 헤드 를 입단 의 한 끝 으로 해 야 합 니까? 답 은 반대 입 니 다. 체인 헤드 를 팀 의 한 끝 으로 하고 체인 꼬리 를 입단 의 한 끝 으로 해 야 합 니 다.
우리 가 실현 한 체인 시 계 는 단일 체인 구조 이기 때문에 이런 상황 에서 체인 의 첫 번 째 는 입단 이 든 팀 의 한 끝 이 든 모두 가능 하지만 체인 의 끝 이 안 되 고 체인 의 끝 은 팀 의 한 끝 이 될 수 밖 에 없다. 만약 에 체인 의 끝 을 팀 의 한 끝 으로 한다 면 팀 의 복잡 도 는 O (n) 가 될 것 이다.네, 링크 를 옮 겨 다 니 며 끝 노드 의 이전 노드 를 찾 은 다음 에 이 노드 의 next 를 null 로 가리 키 면 팀 의 작업 을 완성 할 수 있 습 니 다. 만약 에 더 블 체인 구조 가 괜 찮 으 면 tail 변 수 를 통 해 이전 노드 를 얻 을 수 있 습 니 다. 링크 를 옮 겨 다 니 며 찾 을 필요 가 없습니다. 따라서 우 리 는 체인 의 첫 번 째 를 팀 의 한 끝 으로 하고 체인 의 끝 을 팀 의 한 끝 으로 해 야 합 니 다. 이렇게 하면 체인 의 한 끝 이 없습니다.팀 을 나 가 느 냐, 입단 하 느 냐 의 시간 복잡 도 는 모두 O (1) 다.
구체 적 인 실현 코드 는 다음 과 같다.
/**
* @program: Data-Structure
* @description:
* @author: 01
* @create: 2018-11-09 17:00
**/
public class LinkedListQueue implements Queue {
private class Node {
E e;
Node next;
public Node() {
this(null, null);
}
public Node(E e) {
this(e, null);
}
public Node(E e, Node next) {
this.e = e;
this.next = next;
}
@Override
public String toString() {
return e.toString();
}
}
/**
*
*/
private Node head;
/**
*
*/
private Node tail;
/**
*
*/
private int size;
@Override
public void enqueue(E e) {
if (tail == null) {
//
tail = new Node(e);
head = tail;
} else {
//
tail.next = new Node(e);
tail = tail.next;
}
size++;
}
@Override
public E dequeue() {
if (isEmpty()) {
throw new IllegalArgumentException("Can't dequeue from an empty queue.");
}
//
Node retNode = head;
head = head.next;
retNode.next = null;
if (head == null) {
// ，
tail = null;
}
size--;
return retNode.e;
}
@Override
public E getFront() {
if (isEmpty()) {
throw new IllegalArgumentException("Queue is empty.");
}
return head.e;
}
@Override
public int getSize() {
return size;
}
@Override
public boolean isEmpty() {
return size == 0;
}
@Override
public String toString() {
if (isEmpty()) {
return "[]";
}
StringBuilder sb = new StringBuilder();
sb.append(String.format("LinkedListQueue: size = %d
", getSize()));
sb.append("front [");
Node cur = head;
while (cur != null) {
sb.append(cur.e).append(", ");
cur = cur.next;
}
return sb.append("NULL] tail").toString();
}
} 다음으로 전송:https://blog.51cto.com/zero01/2315226
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
