단일 연결 목록 및 이중 연결 목록 데이터 구조의 Java 시뮬레이션 예
- 高洛峰원래의
- 2017-01-24 16:05:441615검색
단일 연결 목록 시뮬레이션
선형 테이블:
선형 테이블(시퀀스 테이블이라고도 함)은 가장 기본적이고 단순하며 가장 일반적으로 사용되는 데이터 구조입니다.
선형 테이블의 데이터 요소 간의 관계는 일대일 관계입니다. 즉, 첫 번째와 마지막 데이터 요소를 제외하고 다른 데이터 요소는 끝에서 끝까지 연결됩니다.
선형 테이블은 단순한 논리적 구조를 가지고 있어 구현과 운영이 쉽습니다.
실제 응용에서는 선형 테이블이 스택, 큐, 문자열과 같은 특수 선형 테이블 형태로 사용됩니다.
선형 구조의 기본 특성은 다음과 같습니다.
1. 세트에는 "첫 번째 요소"가 하나만 있어야 합니다.
2. 세트에는 "마지막 요소"가 하나만 있어야 합니다.
3. 마지막 요소를 제외한 모든 요소에는 고유한 후속 요소(결과)가 있습니다.
4. 첫 번째 요소를 제외한 모든 요소에는 고유한 전구체(전건)가 있습니다.
연결된 목록: 연결된 목록
연결된 목록은 물리적 저장 단위의 비연속적이고 비순차적인 저장 구조입니다. 데이터 요소의 논리적 순서는 포인터의 연결 순서를 통해 구현됩니다. 연결 목록
각 데이터 항목은 "링크"에 포함되어 있습니다.
링크 포인트는 Link라고 불리는 클래스의 객체입니다. 연결된 목록에는 유사한 링크 포인트가 많이 있으며 각 링크에는 다음 링크 포인트를 참조하는 next 필드가 포함되어 있습니다.
연결된 목록 개체 자체는 첫 번째 링크 지점에 대한 참조를 먼저 저장합니다. (첫 번째가 없으면 위치 지정이 불가능합니다.)
연결된 리스트는 배열처럼 데이터 항목에 직접 접근할 수 없지만(첨자를 사용하여), 찾을 데이터 간의 관계, 즉 다음 항목에 접근해야 합니다. 링크 포인트가 참조하는 링크 필요한 데이터에 접근할 때까지 클릭하고 다음 링크
체인의 선두에 삽입하고 삭제하는 시간 복잡도는 O(1)입니다. 포인터만 변경하면 되기 때문입니다. 지정된 결과 포인트를 찾아 삭제하기 위한 참조의 경우 지정된 노드 뒤에 삽입하면 이 작업은 평균적으로 연결된 목록에 있는 노드의 절반을 검색해야 하며 효율성은 O(N)입니다.
단일 연결 리스트:
선형 리스트를 "노드의 순서"로 표현하는 것을 선형 연결 리스트(단일 연결 리스트)라고 합니다.
연쇄 액세스 데이터 구조로, 집합에 저장됩니다. 임의의 주소가 있는 저장 단위입니다. 선형 테이블의 데이터 요소입니다. (이 저장 단위 그룹은 연속적이거나 불연속적일 수 있습니다)
링크 포인트의 구조:
연결 리스트는 각 노드의 링크 필드를 통해 선형 리스트의 n개 노드를 논리적 순서에 따라 연결합니다.
각 노드에 대해 하나의 링크 필드만 있는 연결 목록을 단일 연결 목록이라고 합니다. 한 방향에서는 후속 노드에 대한 참조만 있습니다.
/**
* 单链表:头插法 后进先出
* 将链表的左边称为链头，右边称为链尾。
* 头插法建单链表是将链表右端看成固定的，链表不断向左延伸而得到的。
* 头插法最先得到的是尾结点
* @author stone
*/
public class SingleLinkedList<T> {
private Link<T> first; //首结点
public SingleLinkedList() {
}
public boolean isEmpty() {
return first == null;
}
public void insertFirst(T data) {// 插入 到 链头
Link<T> newLink = new Link<T>(data);
newLink.next = first; //新结点的next指向上一结点
first = newLink;
}
public Link<T> deleteFirst() {//删除 链头
Link<T> temp = first;
first = first.next; //变更首结点，为下一结点
return temp;
}
public Link<T> find(T t) {
Link<T> find = first;
while (find != null) {
if (!find.data.equals(t)) {
find = find.next;
} else {
break;
}
}
return find;
}
public Link<T> delete(T t) {
if (isEmpty()) {
return null;
} else {
if (first.data.equals(t)) {
Link<T> temp = first;
first = first.next; //变更首结点，为下一结点
return temp;
}
}
Link<T> p = first;
Link<T> q = first;
while (!p.data.equals(t)) {
if (p.next == null) {//表示到链尾还没找到
return null;
} else {
q = p;
p = p.next;
}
}
q.next = p.next;
return p;
}
public void displayList() {//遍历
System.out.println("List (first-->last):");
Link<T> current = first;
while (current != null) {
current.displayLink();
current = current.next;
}
}
public void displayListReverse() {//反序遍历
Link<T> p = first, q = first.next, t;
while (q != null) {//指针反向，遍历的数据顺序向后
t = q.next; //no3
if (p == first) {// 当为原来的头时，头的.next应该置空
p.next = null;
}
q.next = p;// no3 -> no1 pointer reverse
p = q; //start is reverse
q = t; //no3 start
}
//上面循环中的if里，把first.next 置空了, 而当q为null不执行循环时，p就为原来的最且一个数据项，反转后把p赋给first
first = p;
displayList();
}
class Link<T> {//链结点
T data; //数据域
Link<T> next; //后继指针，结点 链域
Link(T data) {
this.data = data;
}
void displayLink() {
System.out.println("the data is " + data.toString());
}
}
public static void main(String[] args) {
SingleLinkedList<Integer> list = new SingleLinkedList<Integer>();
list.insertFirst(33);
list.insertFirst(78);
list.insertFirst(24);
list.insertFirst(22);
list.insertFirst(56);
list.displayList();
list.deleteFirst();
list.displayList();
System.out.println("find:" + list.find(56));
System.out.println("find:" + list.find(33));
System.out.println("delete find:" + list.delete(99));
System.out.println("delete find:" + list.delete(24));
list.displayList();
System.out.println("----reverse----");
list.displayListReverse();
}
}인쇄List (first-->last): the data is 56 the data is 22 the data is 24 the data is 78 the data is 33 List (first-->last): the data is 22 the data is 24 the data is 78 the data is 33 find:null find:linked_list.SingleLinkedList$Link@4b71bbc9 delete find:null delete find:linked_list.SingleLinkedList$Link@17dfafd1 List (first-->last): the data is 22 the data is 78 the data is 33 ----reverse---- List (first-->last): the data is 33 the data is 78 the data is 22
단일 연결 목록: 꼬리 삽입 방식, 후입선출 - 연결 목록의 왼쪽 끝이 고정되면 연결 목록이 오른쪽으로 계속 확장됩니다. 목록을 꼬리 삽입 방법이라고 합니다.
tail 삽입 방식은 연결 리스트 생성 시 헤드 포인터가 고정되어 있으므로 연결 리스트의 오른쪽까지 확장되도록 tail 포인터를 설정해야 합니다.
tail 삽입 방식으로 얻은 첫 번째 사항입니다. 헤드 노드입니다.
public class SingleLinkedList2<T> {
private Link<T> head; //首结点
public SingleLinkedList2() {
}
public boolean isEmpty() {
return head == null;
}
public void insertLast(T data) {//在链尾 插入
Link<T> newLink = new Link<T>(data);
if (head != null) {
Link<T> nextP = head.next;
if (nextP == null) {
head.next = newLink;
} else {
Link<T> rear = null;
while (nextP != null) {
rear = nextP;
nextP = nextP.next;
}
rear.next = newLink;
}
} else {
head = newLink;
}
}
public Link<T> deleteLast() {//删除 链尾
Link<T> p = head;
Link<T> q = head;
while (p.next != null) {// p的下一个结点不为空，q等于当前的p(即q是上一个，p是下一个) 循环结束时，q等于链尾倒数第二个
q = p;
p = p.next;
}
//delete
q.next = null;
return p;
}
public Link<T> find(T t) {
Link<T> find = head;
while (find != null) {
if (!find.data.equals(t)) {
find = find.next;
} else {
break;
}
}
return find;
}
public Link<T> delete(T t) {
if (isEmpty()) {
return null;
} else {
if (head.data.equals(t)) {
Link<T> temp = head;
head = head.next; //变更首结点，为下一结点
return temp;
}
}
Link<T> p = head;
Link<T> q = head;
while (!p.data.equals(t)) {
if (p.next == null) {//表示到链尾还没找到
return null;
} else {
q = p;
p = p.next;
}
}
q.next = p.next;
return p;
}
public void displayList() {//遍历
System.out.println("List (head-->last):");
Link<T> current = head;
while (current != null) {
current.displayLink();
current = current.next;
}
}
public void displayListReverse() {//反序遍历
Link<T> p = head, q = head.next, t;
while (q != null) {//指针反向，遍历的数据顺序向后
t = q.next; //no3
if (p == head) {// 当为原来的头时，头的.next应该置空
p.next = null;
}
q.next = p;// no3 -> no1 pointer reverse
p = q; //start is reverse
q = t; //no3 start
}
//上面循环中的if里，把head.next 置空了, 而当q为null不执行循环时，p就为原来的最且一个数据项，反转后把p赋给head
head = p;
displayList();
}
class Link<T> {//链结点
T data; //数据域
Link<T> next; //后继指针，结点 链域
Link(T data) {
this.data = data;
}
void displayLink() {
System.out.println("the data is " + data.toString());
}
}
public static void main(String[] args) {
SingleLinkedList2<Integer> list = new SingleLinkedList2<Integer>();
list.insertLast(33);
list.insertLast(78);
list.insertLast(24);
list.insertLast(22);
list.insertLast(56);
list.displayList();
list.deleteLast();
list.displayList();
System.out.println("find:" + list.find(56));
System.out.println("find:" + list.find(33));
System.out.println("delete find:" + list.delete(99));
System.out.println("delete find:" + list.delete(78));
list.displayList();
System.out.println("----reverse----");
list.displayListReverse();
}
}
인쇄List (head-->last): the data is 33 the data is 78 the data is 24 the data is 22 the data is 56 List (head-->last): the data is 33 the data is 78 the data is 24 the data is 22 find:null find:linked_list.SingleLinkedList2$Link@4b71bbc9 delete find:null delete find:linked_list.SingleLinkedList2$Link@17dfafd1 List (head-->last): the data is 33 the data is 24 the data is 22 ----reverse---- List (head-->last): the data is 22 the data is 24 the data is 33양단 연결 목록 시뮬레이션 및 연결 목록 사용 스택 및 큐 구현
이중 종료 연결 목록:
이중 종료 연결 목록은 기존 연결 목록과 매우 유사하며 마지막 링크 지점에 참조라는 새로운 속성을 추가합니다.
이렇게 하면 체인 끝에 삽입하기가 매우 쉽습니다. 마지막 노드
를 검색하기 위해 반복하는 대신 새 노드 옆에 있는 후면을 변경하면 됩니다. 따라서 insertFirst 및 insertLast
를 사용하여 링크 헤드를 삭제할 때 참조점만 변경하면 됩니다. 링크를 삭제하면 끝에서 두 번째 노드의 다음은 공백으로 남겨두어야 합니다.
이를 가리키는 참조가 없으므로 작업을 읽으려면 여전히 루프가 필요합니다.
/**
* 双端链表
* @author stone
*/
public class TwoEndpointList<T> {
private Link<T> head; //首结点
private Link<T> rear; //尾部指针
public TwoEndpointList() {
}
public T peekHead() {
if (head != null) {
return head.data;
}
return null;
}
public boolean isEmpty() {
return head == null;
}
public void insertFirst(T data) {// 插入 到 链头
Link<T> newLink = new Link<T>(data);
newLink.next = head; //新结点的next指向上一结点
head = newLink;
}
public void insertLast(T data) {//在链尾 插入
Link<T> newLink = new Link<T>(data);
if (head == null) {
rear = null;
}
if (rear != null) {
rear.next = newLink;
} else {
head = newLink;
head.next = rear;
}
rear = newLink; //下次插入时，从rear处插入
}
public T deleteHead() {//删除 链头
if (isEmpty()) return null;
Link<T> temp = head;
head = head.next; //变更首结点，为下一结点
if (head == null) {
<span style="white-space:pre"> </span>rear = head;
}
return temp.data;
}
public T find(T t) {
if (isEmpty()) {
return null;
}
Link<T> find = head;
while (find != null) {
if (!find.data.equals(t)) {
find = find.next;
} else {
break;
}
}
if (find == null) {
return null;
}
return find.data;
}
public T delete(T t) {
if (isEmpty()) {
return null;
} else {
if (head.data.equals(t)) {
Link<T> temp = head;
head = head.next; //变更首结点，为下一结点
return temp.data;
}
}
Link<T> p = head;
Link<T> q = head;
while (!p.data.equals(t)) {
if (p.next == null) {//表示到链尾还没找到
return null;
} else {
q = p;
p = p.next;
}
}
q.next = p.next;
return p.data;
}
public void displayList() {//遍历
System.out.println("List (head-->last):");
Link<T> current = head;
while (current != null) {
current.displayLink();
current = current.next;
}
}
public void displayListReverse() {//反序遍历
if (isEmpty()) {
return;
}
Link<T> p = head, q = head.next, t;
while (q != null) {//指针反向，遍历的数据顺序向后
t = q.next; //no3
if (p == head) {// 当为原来的头时，头的.next应该置空
p.next = null;
}
q.next = p;// no3 -> no1 pointer reverse
p = q; //start is reverse
q = t; //no3 start
}
//上面循环中的if里，把head.next 置空了, 而当q为null不执行循环时，p就为原来的最且一个数据项，反转后把p赋给head
head = p;
displayList();
}
class Link<T> {//链结点
T data; //数据域
Link<T> next; //后继指针，结点 链域
Link(T data) {
this.data = data;
}
void displayLink() {
System.out.println("the data is " + data.toString());
}
}
public static void main(String[] args) {
TwoEndpointList<Integer> list = new TwoEndpointList<Integer>();
list.insertLast(1);
list.insertFirst(2);
list.insertLast(3);
list.insertFirst(4);
list.insertLast(5);
list.displayList();
list.deleteHead();
list.displayList();
System.out.println("find:" + list.find(6));
System.out.println("find:" + list.find(3));
System.out.println("delete find:" + list.delete(6));
System.out.println("delete find:" + list.delete(5));
list.displayList();
System.out.println("----reverse----");
list.displayListReverse();
}
}
인쇄List (head-->last): the data is 4 the data is 2 the data is 1 the data is 3 the data is 5 List (head-->last): the data is 2 the data is 1 the data is 3 the data is 5 find:null find:3 delete find:null delete find:5 List (head-->last): the data is 2 the data is 1 the data is 3 ----reverse---- List (head-->last): the data is 3 the data is 1 the data is 2연결된 목록을 사용하여 스택을 구현합니다.
이 클래스는 이중 종료 연결 목록을 사용하여 다음을 구현합니다.
public class LinkStack<T> {
private TwoEndpointList<T> datas;
public LinkStack() {
datas = new TwoEndpointList<T>();
}
// 入栈
public void push(T data) {
datas.insertFirst(data);
}
// 出栈
public T pop() {
return datas.deleteHead();
}
// 查看栈顶
public T peek() {
return datas.peekHead();
}
//栈是否为空
public boolean isEmpty() {
return datas.isEmpty();
}
public static void main(String[] args) {
LinkStack<Integer> stack = new LinkStack<Integer>();
for (int i = 0; i < 5; i++) {
stack.push(i);
}
for (int i = 0; i < 5; i++) {
Integer peek = stack.peek();
System.out.println("peek:" + peek);
}
for (int i = 0; i < 6; i++) {
Integer pop = stack.pop();
System.out.println("pop:" + pop);
}
System.out.println("----");
for (int i = 5; i > 0; i--) {
stack.push(i);
}
for (int i = 5; i > 0; i--) {
Integer peek = stack.peek();
System.out.println("peek:" + peek);
}
for (int i = 5; i > 0; i--) {
Integer pop = stack.pop();
System.out.println("pop:" + pop);
}
}
}
인쇄peek:4 peek:4 peek:4 peek:4 peek:4 pop:4 pop:3 pop:2 pop:1 pop:0 pop:null ---- peek:1 peek:1 peek:1 peek:1 peek:1 pop:1 pop:2 pop:3 pop:4 pop:5연결 목록 구현 대기열 이중 종료 연결 목록을 사용한 구현:
public class LinkQueue<T> {
private TwoEndpointList<T> list;
public LinkQueue() {
list = new TwoEndpointList<T>();
}
//插入队尾
public void insert(T data) {
list.insertLast(data);
}
//移除队头
public T remove() {
return list.deleteHead();
}
//查看队头
public T peek() {
return list.peekHead();
}
public boolean isEmpty() {
return list.isEmpty();
}
public static void main(String[] args) {
LinkQueue<Integer> queue = new LinkQueue<Integer>();
for (int i = 1; i < 5; i++) {
queue.insert(i);
}
for (int i = 1; i < 5; i++) {
Integer peek = queue.peek();
System.out.println("peek:" + peek);
}
for (int i = 1; i < 5; i++) {
Integer remove = queue.remove();
System.out.println("remove:" + remove);
}
System.out.println("----");
for (int i = 5; i > 0; i--) {
queue.insert(i);
}
for (int i = 5; i > 0; i--) {
Integer peek = queue.peek();
System.out.println("peek2:" + peek);
}
for (int i = 5; i > 0; i--) {
Integer remove = queue.remove();
System.out.println("remove:" + remove);
}
}
}
인쇄peek:1 peek:1 peek:1 peek:1 remove:1 remove:2 remove:3 remove:4 ---- peek2:5 peek2:5 peek2:5 peek2:5 peek2:5 remove:5 remove:4 remove:3 remove:2 remove:1단일 연결 목록 및 이중 연결 목록 데이터 구조의 Java 시뮬레이션에 대한 더 많은 예를 보려면 PHP 중국어 웹사이트에서 관련 기사를 주목하세요!
성명：
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.