Java模拟单链表和双端链表数据结构的实例讲解

Java模拟单链表和双端链表数据结构的实例讲解

模拟单链表

线性表：

线性表（亦作顺序表）是最基本、最简单、也是最常用的一种数据结构。

线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的。

线性表的逻辑结构简单，便于实现和操作。

在实际应用中，线性表都是以栈、队列、字符串等特殊线性表的形式来使用的。

线性结构的基本特征为:

1．集合中必存在唯一的一个“第一元素”；

2．集合中必存在唯一的一个 “最后元素” ；

3．除最后一个元素之外，均有 唯一的后继(后件)；

4．除第一个元素之外，均有 唯一的前驱(前件)。

链表：linked list

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的

每个数据项都被包含在“链结点”（Link）中。

链结点是一个类的对象，这类可叫做Link。链表中有许多类似的链结点，每个Link中都中包含有一个对下一个链结点引用的字段next。

链表对象本身保存了一个指向第一个链结点的引用first。(若没有first，则无法定位)

链表不能像数组那样(利用下标)直接访问到数据项，而需要用数据间的关系来定位，即访问链结点所引用的下一个链结点，而后再下一个，直至访问到需要的数据

在链头插入和删除的时间复杂度为O(1)，因为只需要改变引用的指向即可

而查找、删除指定结点、在指定结点后插入，这些操作都需要平均都需要搜索链表中的一半结点，效率为O(N)。

单链表：

以“结点的序列”表示线性表 称作线性链表（单链表）

是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。(这组存储单元既可以是连续的，也可以是不连续的)

链结点的结构：

存放结点值的数据域data;存放结点的引用 的指针域（链域）next

链表通过每个结点的链域将线性表的n个结点按其逻辑顺序链接在一起的。

每个结点只有一个链域的链表称为单链表（Single Linked List） ， 一个方向, 只有后继结节的引用

/**

* 单链表:头插法 后进先出

* 将链表的左边称为链头，右边称为链尾。

* 头插法建单链表是将链表右端看成固定的，链表不断向左延伸而得到的。

* 头插法最先得到的是尾结点

* @author stone

*/

public class SingleLinkedList {

private Link first; //首结点

public SingleLinkedList() {

}

public boolean isEmpty() {

return first == null;

}

public void insertFirst(T data) {// 插入 到 链头

Link newLink = new Link(data);

newLink.next = first; //新结点的next指向上一结点

first = newLink;

}

public Link deleteFirst() {//删除 链头

Link temp = first;

first = first.next; //变更首结点，为下一结点

return temp;

}

public Link find(T t) {

Link find = first;

while (find != null) {

if (!find.data.equals(t)) {

find = find.next;

} else {

break;

}

}

return find;

}

public Link delete(T t) {

if (isEmpty()) {

return null;

} else {

if (first.data.equals(t)) {

Link temp = first;

first = first.next; //变更首结点，为下一结点

return temp;

}

}

Link p = first;

Link 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 current = first;

while (current != null) {

current.displayLink();

current = current.next;

}

}

public void displayListReverse() {//反序遍历

Link 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 data; //数据域

Link next; //后继指针，结点 链域

Link(T data) {

this.data = data;

}

void displayLink() {

System.out.println("the data is " + data.toString());

}

}

public static void main(String[] args) {

SingleLinkedList list = new SingleLinkedList();

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

单链表:尾插法 、后进先出 ——若将链表的左端固定，链表不断向右延伸，这种建立链表的方法称为尾插法。 

尾插法建立链表时，头指针固定不动，故必须设立一个尾部的指针，向链表右边延伸， 

尾插法最先得到的是头结点。

public class SingleLinkedList2 {

private Link head; //首结点

public SingleLinkedList2() {

}

public boolean isEmpty() {

return head == null;

}

public void insertLast(T data) {//在链尾 插入

Link newLink = new Link(data);

if (head != null) {

Link nextP = head.next;

if (nextP == null) {

head.next = newLink;

} else {

Link rear = null;

while (nextP != null) {

rear = nextP;

nextP = nextP.next;

}

rear.next = newLink;

}

} else {

head = newLink;

}

}

public Link deleteLast() {//删除 链尾

Link p = head;

Link 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 find(T t) {

Link find = head;

while (find != null) {

if (!find.data.equals(t)) {

find = find.next;

} else {

break;

}

}

return find;

}

public Link delete(T t) {

if (isEmpty()) {

return null;

} else {

if (head.data.equals(t)) {

Link temp = head;

head = head.next; //变更首结点，为下一结点

return temp;

}

}

Link p = head;

Link 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 current = head;

while (current != null) {

current.displayLink();

current = current.next;

}

}

public void displayListReverse() {//反序遍历

Link 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 data; //数据域

Link next; //后继指针，结点 链域

Link(T data) {

this.data = data;

}

void displayLink() {

System.out.println("the data is " + data.toString());

}

}

public static void main(String[] args) {

SingleLinkedList2 list = new SingleLinkedList2();

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

模拟双端链表，以链表实现栈和队列

双端链表：

双端链表与传统链表非常相似.只是新增了一个属性-即对最后一个链结点的引用rear

这样在链尾插入会变得非常容易，只需改变rear的next为新增的结点即可，而不需要循环搜索到最后一个节点

所以有insertFirst、insertLast

删除链头时，只需要改变引用指向即可；删除链尾时，需要将倒数第二个结点的next置空，

而没有一个引用是指向它的，所以还是需要循环来读取操作

/**

* 双端链表

* @author stone

*/

public class TwoEndpointList {

private Link head; //首结点

private Link 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 newLink = new Link(data);

newLink.nexljYwxRt = head; //新结点的next指向上一结点

head = newLink;

}

public void insertLast(T data) {//在链尾 插入

Link newLink = new Link(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 temp = head;

head = head.next; //变更首结点，为下一结点

if (head == null) {

rear = head;

}

return temp.data;

}

public T find(T t) {

if (isEmpty()) {

return null;

}

Link 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 temp = head;

head = head.next; //变更首结点，为下一结点

return temp.data;

}

}

Link p = head;

Link 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 current = head;

while (current != null) {

current.displayLink();

current = current.next;

}

}

public void displayListReverse() {//反序遍历

if (isEmpty()) {

return;

}

Link 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 data; //数据域

Link next; //后继指针，结点 链域

Link(T data) {

this.data = data;

}

void displayLink() {

System.out.println("the data is " + data.toString());

}

}

public static void main(String[] args) {

TwoEndpointList list = new TwoEndpointList();

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 {

private TwoEndpointList datas;

public LinkStack() {

datas = new TwoEndpointList();

}

// 入栈

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 stack = new LinkStack();

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 {

private TwoEndpointList list;

public LinkQueue() {

list = new TwoEndpointList();

}

//插入队尾

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 queue = new LinkQueue();

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

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。