Java数据结构和算法--链表
(1)简单链表
Java代码
package ChapterFive;
class Link<E> {
public E data;
public Link<E> next;
public Link(E data) {
this.data = data;
}
}
class LinkList<E> {
public Link<E> first;
//链表中数据项的个数
public int size;
public LinkList() {
first = null;
size = 0;
}
//在表头插入新的数据
public void insertFirst(E value) {
Link<E> link = new Link<E>(value);
link.next = first;
first = link;
size++;
}
//判断链表是否为空
public boolean isEmpty() {
return size == 0;
}
//删除表头
public Link<E> deleteFirst() {
Link<E> temp = first;
first = first.next;
size--;
return temp;
}
//输出链表中的所有数据
public void display() {
Link<E> curr = first;
while (curr != null) {
System.out.print(curr.data + " ");
curr = curr.next;
}
System.out.println();
}
//返回链表中数据项的个数
public int size() {
return size;
}
//获取从头至尾的第i个数据项
public Link<E> get(int i) {
if (i > size() - 1 || i < 0)
try {
throw new IndexOutOfBoundsException();
} catch (Exception e) {
e.printStackTrace();
}
Link<E> curr = first;
for (int n = 0; n < size(); n++) {
if (n == i)
return curr;
else
curr = curr.next;
}
return null;
}
//输出从头至尾的第i个数据项
public void remove(int i) {
if (i == 0)
deleteFirst();
else if (i == size() - 1)
get(i - 1).next = null;
else {
get(i - 1).next = get(i + 1);
}
size--;
}
}
public class Link_list {
public static void main(String[] args) {
LinkList<Long> ll = new LinkList<Long>();
for (int i = 0; i < 10; i++) {
Long value = (long) (Math.random() * 100);
ll.insertFirst(value);
}
ll.display();
while (!ll.isEmpty()) {
ll.deleteFirst();
ll.display();
}
System.out.println("Ok");
}
}
package ChapterFive;
class Link<E> {
public E data;
public Link<E> next;
public Link(E data) {
this.data = data;
}
}
class LinkList<E> {
public Link<E> first;
//链表中数据项的个数
public int size;
public LinkList() {
first = null;
size = 0;
}
//在表头插入新的数据
public void insertFirst(E value) {
Link<E> link = new Link<E>(value);
link.next = first;
first = link;
size++;
}
//判断链表是否为空
public boolean isEmpty() {
return size == 0;
}
//删除表头
public Link<E> deleteFirst() {
Link<E> temp = first;
first = first.next;
size--;
return temp;
}
//输出链表中的所有数据
public void display() {
Link<E> curr = first;
while (curr != null) {
System.out.print(curr.data + " ");
curr = curr.next;
}
System.out.println();
}
//返回链表中数据项的个数
public int size() {
return size;
}
//获取从头至尾的第i个数据项
public Link<E> get(int i) {
if (i > size() - 1 || i < 0)
try {
throw new IndexOutOfBoundsException();
} catch (Exception e) {
e.printStackTrace();
}
Link<E> curr = first;
for (int n = 0; n < size(); n++) {
if (n == i)
return curr;
else
curr = curr.next;
}
return null;
}
//输出从头至尾的第i个数据项
public void remove(int i) {
if (i == 0)
deleteFirst();
else if (i == size() - 1)
get(i - 1).next = null;
else {
get(i - 1).next = get(i + 1);
}
size--;
}
}
public class Link_list {
public static void main(String[] args) {
LinkList<Long> ll = new LinkList<Long>();
for (int i = 0; i < 10; i++) {
Long value = (long) (Math.random() * 100);
ll.insertFirst(value);
}
ll.display();
while (!ll.isEmpty()) {
ll.deleteFirst();
ll.display();
}
System.out.println("Ok");
}
}
(2)链栈
Java代码
package ChapterFive;
class LinkStack<E> {
LinkList<E> linkList;
int size;
public LinkStack() {
size = 0;
linkList = new LinkList<E>();
}
//入栈
public void push(E value) {
linkList.insertFirst(value);
size++;
}
//出栈
public Link<E> pop() {
size--;
return linkList.deleteFirst();
}
//返回栈顶元素
public Link<E> top() {
return linkList.first;
}
//判断栈是否为空
public boolean isEmpty() {
return size == 0;
}
//显示栈中的全部数据
public void display() {
linkList.display();
}
}
public class Link_stack {
public static void main(String[] args) {
LinkStack<Long> ls = new LinkStack<Long>();
for (int i = 0; i < 10; i++) {
Long value = new Long((long) (Math.random() * 100));
ls.push(value);
}
while (!ls.isEmpty()) {
ls.pop();
ls.display();
}
System.out.println("Ok");
}
}
package ChapterFive;
class LinkStack<E> {
LinkList<E> linkList;
int size;
public LinkStack() {
size = 0;
linkList = new LinkList<E>();
}
//入栈
public void push(E value) {
linkList.insertFirst(value);
size++;
}
//出栈
public Link<E> pop() {
size--;
return linkList.deleteFirst();
}
//返回栈顶元素
public Link<E> top() {
return linkList.first;
}
//判断栈是否为空
public boolean isEmpty() {
return size == 0;
}
//显示栈中的全部数据
public void display() {
linkList.display();
}
}
public class Link_stack {
public static void main(String[] args) {
LinkStack<Long> ls = new LinkStack<Long>();
for (int i = 0; i < 10; i++) {
Long value = new Long((long) (Math.random() * 100));
ls.push(value);
}
while (!ls.isEmpty()) {
ls.pop();
ls.display();
}
System.out.println("Ok");
}
}
(3)有序表
Java代码
package ChapterFive;
class SortedLink {
public Link<Long> first;
int size;
public SortedLink() {
first = null;
size = 0;
}
//向有序链表中插入数据
public void insert(long value) {
Link<Long> newLink = new Link<Long>(value);
Link<Long> previous = null;
Link<Long> curr = first;
while (curr != null && (value > curr.data)) {
previous = curr;
curr = curr.next;
}
if (previous == null)// 链表为空(在表头插入)
first = newLink;
else
previous.next = newLink;//插入新的节点
newLink.next = curr;
size++;
}
//删除第一个节点
public Link<Long> remove() {
Link<Long> temp = first;
first = first.next;
size--;
return temp;
}
//判断链表是否为空
public boolean isEmpty() {
return size == 0;
}
//输出链表的所有数据
public void display() {
Link<Long> curr = first;
while (curr != null) {
System.out.print(curr.data + " ");
curr = curr.next;
}
System.out.println();
}
}
public class SortedLinkApp {
public static void main(String[] args) {
SortedLink sl = new SortedLink();
for (int i = 0; i < 10; i++) {
sl.insert((long) (Math.random() * 100));
}
while (!sl.isEmpty()) {
sl.remove();
sl.display();
}
}
}
package ChapterFive;
class SortedLink {
public Link<Long> first;
int size;
public SortedLink() {
first = null;
size = 0;
}
//向有序链表中插入数据
public void insert(long value) {
Link<Long> newLink = new Link<Long>(value);
Link<Long> previous = null;
Link<Long> curr = first;
while (curr != null && (value > curr.data)) {
previous = curr;
curr = curr.next;
}
if (previous == null)// 链表为空(在表头插入)
first = newLink;
else
previous.next = newLink;//插入新的节点
newLink.next = curr;
size++;
}
//删除第一个节点
public Link<Long> remove() {
Link<Long> temp = first;
first = first.next;
size--;
return temp;
}
//判断链表是否为空
public boolean isEmpty() {
return size == 0;
}
//输出链表的所有数据
public void display() {
Link<Long> curr = first;
while (curr != null) {
System.out.print(curr.data + " ");
curr = curr.next;
}
System.out.println();
}
}
public class SortedLinkApp {
public static void main(String[] args) {
SortedLink sl = new SortedLink();
for (int i = 0; i < 10; i++) {
sl.insert((long) (Math.random() * 100));
}
while (!sl.isEmpty()) {
sl.remove();
sl.display();
}
}
}
(4)双向链表
Java代码
package ChapterFive;
class DoubleLink<E> {
public Link<E> first;
public Link<E> last;
int size;
@SuppressWarnings("hiding")
class Link<E> {
public E data;
public Link<E> next;// 链表的下一项
public Link<E> previous;// 链表的前一项
public Link(E value) {
this.data = value;
}
}
public DoubleLink() {
first = null;
last = null;
size = 0;
}
// 在链表的首部插入一项
public void insertFirst(E value) {
Link<E> newLink = new Link<E>(value);
if (isEmpty())// 如果链表为空则first == last
last = newLink;
else
first.previous = newLink;// 确定原first与newLink的前后关系
newLink.next = first;
first = newLink;// 设置新的first值
size++;
}
// 在链表的尾部插入一项
public void insertLast(E value) {
Link<E> newLink = new Link<E>(value);
if (isEmpty())// 如果链表为空则last == first
first = newLink;
else {
last.next = newLink;// 确定原last与newLink的前后关系
newLink.previous = last;
}
last = newLink;// 设置新的last值
size++;
}
// 删除双向链表的表头
public Link<E> deleteFirst() {
Link<E> temp = first;
if (first.next == null)// 链表中只有一项数据
last = null;
else
first.next.previous = null;// 销毁原链表的头部
first = first.next;
size--;
return temp;
}
// 删除链表的最后一项
public Link<E> deleteLast() {
Link<E> temp = last;
if (first.next == null)// 链表中只有一项数据
first = null;
else
last.previous.next = null;// 销毁原链表的尾部
last = last.previous;
size--;
return temp;
}
// 判断链表是否为空
public boolean isEmpty() {
return size == 0;
}
// 输出链表中的所有数据项
public void display() {
Link<E> curr = first;
while (curr != null) {
System.out.print(curr.data + " ");
curr = curr.next;
}
System.out.println();
}
}
public class DoubleLinkApp {
public static void main(String[] args) {
DoubleLink<Integer> dl = new DoubleLink<Integer>();
for (int i = 0; i < 5; i++) {
dl.insertFirst((int) (Math.random() * 100));
}
for (int i = 0; i < 5; i++) {
dl.insertLast((int) (Math.random() * 100));
}
dl.display();
while (!dl.isEmpty()) {
dl.deleteFirst();
dl.deleteLast();
dl.display();
}
System.out.println("Ok");
}
}
Java代码
package ChapterFive;
class Link<E> {
public E data;
public Link<E> next;
public Link(E data) {
this.data = data;
}
}
class LinkList<E> {
public Link<E> first;
//链表中数据项的个数
public int size;
public LinkList() {
first = null;
size = 0;
}
//在表头插入新的数据
public void insertFirst(E value) {
Link<E> link = new Link<E>(value);
link.next = first;
first = link;
size++;
}
//判断链表是否为空
public boolean isEmpty() {
return size == 0;
}
//删除表头
public Link<E> deleteFirst() {
Link<E> temp = first;
first = first.next;
size--;
return temp;
}
//输出链表中的所有数据
public void display() {
Link<E> curr = first;
while (curr != null) {
System.out.print(curr.data + " ");
curr = curr.next;
}
System.out.println();
}
//返回链表中数据项的个数
public int size() {
return size;
}
//获取从头至尾的第i个数据项
public Link<E> get(int i) {
if (i > size() - 1 || i < 0)
try {
throw new IndexOutOfBoundsException();
} catch (Exception e) {
e.printStackTrace();
}
Link<E> curr = first;
for (int n = 0; n < size(); n++) {
if (n == i)
return curr;
else
curr = curr.next;
}
return null;
}
//输出从头至尾的第i个数据项
public void remove(int i) {
if (i == 0)
deleteFirst();
else if (i == size() - 1)
get(i - 1).next = null;
else {
get(i - 1).next = get(i + 1);
}
size--;
}
}
public class Link_list {
public static void main(String[] args) {
LinkList<Long> ll = new LinkList<Long>();
for (int i = 0; i < 10; i++) {
Long value = (long) (Math.random() * 100);
ll.insertFirst(value);
}
ll.display();
while (!ll.isEmpty()) {
ll.deleteFirst();
ll.display();
}
System.out.println("Ok");
}
}
package ChapterFive;
class Link<E> {
public E data;
public Link<E> next;
public Link(E data) {
this.data = data;
}
}
class LinkList<E> {
public Link<E> first;
//链表中数据项的个数
public int size;
public LinkList() {
first = null;
size = 0;
}
//在表头插入新的数据
public void insertFirst(E value) {
Link<E> link = new Link<E>(value);
link.next = first;
first = link;
size++;
}
//判断链表是否为空
public boolean isEmpty() {
return size == 0;
}
//删除表头
public Link<E> deleteFirst() {
Link<E> temp = first;
first = first.next;
size--;
return temp;
}
//输出链表中的所有数据
public void display() {
Link<E> curr = first;
while (curr != null) {
System.out.print(curr.data + " ");
curr = curr.next;
}
System.out.println();
}
//返回链表中数据项的个数
public int size() {
return size;
}
//获取从头至尾的第i个数据项
public Link<E> get(int i) {
if (i > size() - 1 || i < 0)
try {
throw new IndexOutOfBoundsException();
} catch (Exception e) {
e.printStackTrace();
}
Link<E> curr = first;
for (int n = 0; n < size(); n++) {
if (n == i)
return curr;
else
curr = curr.next;
}
return null;
}
//输出从头至尾的第i个数据项
public void remove(int i) {
if (i == 0)
deleteFirst();
else if (i == size() - 1)
get(i - 1).next = null;
else {
get(i - 1).next = get(i + 1);
}
size--;
}
}
public class Link_list {
public static void main(String[] args) {
LinkList<Long> ll = new LinkList<Long>();
for (int i = 0; i < 10; i++) {
Long value = (long) (Math.random() * 100);
ll.insertFirst(value);
}
ll.display();
while (!ll.isEmpty()) {
ll.deleteFirst();
ll.display();
}
System.out.println("Ok");
}
}
(2)链栈
Java代码
package ChapterFive;
class LinkStack<E> {
LinkList<E> linkList;
int size;
public LinkStack() {
size = 0;
linkList = new LinkList<E>();
}
//入栈
public void push(E value) {
linkList.insertFirst(value);
size++;
}
//出栈
public Link<E> pop() {
size--;
return linkList.deleteFirst();
}
//返回栈顶元素
public Link<E> top() {
return linkList.first;
}
//判断栈是否为空
public boolean isEmpty() {
return size == 0;
}
//显示栈中的全部数据
public void display() {
linkList.display();
}
}
public class Link_stack {
public static void main(String[] args) {
LinkStack<Long> ls = new LinkStack<Long>();
for (int i = 0; i < 10; i++) {
Long value = new Long((long) (Math.random() * 100));
ls.push(value);
}
while (!ls.isEmpty()) {
ls.pop();
ls.display();
}
System.out.println("Ok");
}
}
package ChapterFive;
class LinkStack<E> {
LinkList<E> linkList;
int size;
public LinkStack() {
size = 0;
linkList = new LinkList<E>();
}
//入栈
public void push(E value) {
linkList.insertFirst(value);
size++;
}
//出栈
public Link<E> pop() {
size--;
return linkList.deleteFirst();
}
//返回栈顶元素
public Link<E> top() {
return linkList.first;
}
//判断栈是否为空
public boolean isEmpty() {
return size == 0;
}
//显示栈中的全部数据
public void display() {
linkList.display();
}
}
public class Link_stack {
public static void main(String[] args) {
LinkStack<Long> ls = new LinkStack<Long>();
for (int i = 0; i < 10; i++) {
Long value = new Long((long) (Math.random() * 100));
ls.push(value);
}
while (!ls.isEmpty()) {
ls.pop();
ls.display();
}
System.out.println("Ok");
}
}
(3)有序表
Java代码
package ChapterFive;
class SortedLink {
public Link<Long> first;
int size;
public SortedLink() {
first = null;
size = 0;
}
//向有序链表中插入数据
public void insert(long value) {
Link<Long> newLink = new Link<Long>(value);
Link<Long> previous = null;
Link<Long> curr = first;
while (curr != null && (value > curr.data)) {
previous = curr;
curr = curr.next;
}
if (previous == null)// 链表为空(在表头插入)
first = newLink;
else
previous.next = newLink;//插入新的节点
newLink.next = curr;
size++;
}
//删除第一个节点
public Link<Long> remove() {
Link<Long> temp = first;
first = first.next;
size--;
return temp;
}
//判断链表是否为空
public boolean isEmpty() {
return size == 0;
}
//输出链表的所有数据
public void display() {
Link<Long> curr = first;
while (curr != null) {
System.out.print(curr.data + " ");
curr = curr.next;
}
System.out.println();
}
}
public class SortedLinkApp {
public static void main(String[] args) {
SortedLink sl = new SortedLink();
for (int i = 0; i < 10; i++) {
sl.insert((long) (Math.random() * 100));
}
while (!sl.isEmpty()) {
sl.remove();
sl.display();
}
}
}
package ChapterFive;
class SortedLink {
public Link<Long> first;
int size;
public SortedLink() {
first = null;
size = 0;
}
//向有序链表中插入数据
public void insert(long value) {
Link<Long> newLink = new Link<Long>(value);
Link<Long> previous = null;
Link<Long> curr = first;
while (curr != null && (value > curr.data)) {
previous = curr;
curr = curr.next;
}
if (previous == null)// 链表为空(在表头插入)
first = newLink;
else
previous.next = newLink;//插入新的节点
newLink.next = curr;
size++;
}
//删除第一个节点
public Link<Long> remove() {
Link<Long> temp = first;
first = first.next;
size--;
return temp;
}
//判断链表是否为空
public boolean isEmpty() {
return size == 0;
}
//输出链表的所有数据
public void display() {
Link<Long> curr = first;
while (curr != null) {
System.out.print(curr.data + " ");
curr = curr.next;
}
System.out.println();
}
}
public class SortedLinkApp {
public static void main(String[] args) {
SortedLink sl = new SortedLink();
for (int i = 0; i < 10; i++) {
sl.insert((long) (Math.random() * 100));
}
while (!sl.isEmpty()) {
sl.remove();
sl.display();
}
}
}
(4)双向链表
Java代码
package ChapterFive;
class DoubleLink<E> {
public Link<E> first;
public Link<E> last;
int size;
@SuppressWarnings("hiding")
class Link<E> {
public E data;
public Link<E> next;// 链表的下一项
public Link<E> previous;// 链表的前一项
public Link(E value) {
this.data = value;
}
}
public DoubleLink() {
first = null;
last = null;
size = 0;
}
// 在链表的首部插入一项
public void insertFirst(E value) {
Link<E> newLink = new Link<E>(value);
if (isEmpty())// 如果链表为空则first == last
last = newLink;
else
first.previous = newLink;// 确定原first与newLink的前后关系
newLink.next = first;
first = newLink;// 设置新的first值
size++;
}
// 在链表的尾部插入一项
public void insertLast(E value) {
Link<E> newLink = new Link<E>(value);
if (isEmpty())// 如果链表为空则last == first
first = newLink;
else {
last.next = newLink;// 确定原last与newLink的前后关系
newLink.previous = last;
}
last = newLink;// 设置新的last值
size++;
}
// 删除双向链表的表头
public Link<E> deleteFirst() {
Link<E> temp = first;
if (first.next == null)// 链表中只有一项数据
last = null;
else
first.next.previous = null;// 销毁原链表的头部
first = first.next;
size--;
return temp;
}
// 删除链表的最后一项
public Link<E> deleteLast() {
Link<E> temp = last;
if (first.next == null)// 链表中只有一项数据
first = null;
else
last.previous.next = null;// 销毁原链表的尾部
last = last.previous;
size--;
return temp;
}
// 判断链表是否为空
public boolean isEmpty() {
return size == 0;
}
// 输出链表中的所有数据项
public void display() {
Link<E> curr = first;
while (curr != null) {
System.out.print(curr.data + " ");
curr = curr.next;
}
System.out.println();
}
}
public class DoubleLinkApp {
public static void main(String[] args) {
DoubleLink<Integer> dl = new DoubleLink<Integer>();
for (int i = 0; i < 5; i++) {
dl.insertFirst((int) (Math.random() * 100));
}
for (int i = 0; i < 5; i++) {
dl.insertLast((int) (Math.random() * 100));
}
dl.display();
while (!dl.isEmpty()) {
dl.deleteFirst();
dl.deleteLast();
dl.display();
}
System.out.println("Ok");
}
}
相关推荐
javalist数据结构_Java数据结构-------List 三种List:ArrayList,Vector,LinkedList 类继承关系图 ArrayList和Vector通过数组实现,⼏乎使⽤了相同的算法;区别是ArrayList不是线程安全的,Vector绝⼤多数⽅法做了...
《Java数据结构和算法》(第2版)介绍了计算机编程中使用的数据结构和算法,对于在计算机应用中如何操作和管理数据以取得最优性能提供了深入浅出的讲解。全书共分为15章,分别讲述了基本概念、数组、简单排序、堆和...
数据结构与算法----线性表及Java实现顺序表、链表、栈、队列 定义线性表节点的结构.pdf
内容包括: 稀疏数组、单向队列、环形队列、单向链表、双向链表、环形链表、约瑟夫问题、栈、前缀、中缀、后缀表达式、中缀表达式转换为后缀表达式、递归与回溯、迷宫问题、八皇后问题、算法的时间复杂度、冒泡排序、...
java 数据结构和算法, 排序算法, 数组,链表,二叉树
包含了各种数据结构和算法(java)的实现方式和详解(图解),包括单双链表、环形链表(约瑟夫问题)、栈、后缀表达式、中缀表达式转后缀表达式、迷宫问题、八大排序算法、多种查找算法、哈希表、二叉树实现以及操作...
《Java数据结构和算法》(第2版)介绍了计算机编程中使用的数据结构和算法,对于在计算机应用中如何操作和管理数据以取得最优性能提供了深入浅出的讲解。全书共分为15章,分别讲述了基本概念、数组、简单排序、堆和...
JAVA数据结构与算法课程第05课双端链表和双向链表.mp4JAVA数据结构与算法课程第06课递归的应用.mp4JAVA数据结构与算法课程第07课递归的高级应用.mp4JAVA数据结构与算法课程第08课希尔排序.mp4JAVA数据结构与算法课程...
介绍了计算机编程中使用的...《Java数据结构和算法》(第2版)提供了学完一门编程语言后进一步需要知道的知识。本书所涵盖的内容通常作为大学或学院中计算机系二年级的课程,在学生掌握了编程的基础后才开始本书的学习。
算法与数据结构它们分别涵盖了以下主要内容: 数据结构(Data Structures): ...学习算法与数据结构不仅有助于理解程序的内部工作原理,更能帮助开发人员编写出高效、稳定和易于维护的软件系统。
Java数据结构和算法介绍了计算机编程中使用的数据结构和算法,对于在计算机应用中如何操作和管理数据以取得最优性能提供了深入浅出的讲解。全书共分为15章,分别讲述了基本概念、数组、简单排序、堆和队列、链表、...
数据结构-栈与队列,链表,递归,简单排序到高级排序的算法的详细笔记,本人根据视频学习进行的数据结构记录。适合入门算法学习初级篇
以下是关于Java数据结构和算法的一些介绍: Java作为一种流行的编程语言,在数据结构和算法的实现方面有着广泛的应用。数据结构指的是在计算机中组织和存储数据的方式,算法则是明确定义的解决特定问题的规则和步骤。...
算法与数据结构涵盖了以下主要内容: 数据结构(Data Structures): 逻辑结构:描述数据元素之间...学习算法与数据结构不仅有助于理解程序的内部工作原理,更能帮助开发人员编写出高效、稳定和易于维护的软件系统。
书名:数据结构Java版 图书编号:2086963 出版社:清华大学 定价:118.0 ISBN:730213544 作者:(美)福特(Ford,W.H.),(美)托普(Topp,W.R.) 著,梁志敏 译 出版日期:2006-11-11 版次: 开本: 简介: 本书...
java数组和链表底层-链表的底层原理和实现 数组和链表.pdf
Java数据结构和算法 第0讲 综述 参考教材:Java数据结构和算法(第二版),[美] Robert lafore 1. 数据结构的特性 "数据结构"优点 "缺点 " "数组 "插入快;如果知道下标,可以非常快"查找慢,删除慢,大小固定" " ...
逻辑结构:描述数据元素之间的逻辑关系,如线性结构(如数组、链表)、树形结构(如二叉树、堆、B树...学习算法与数据结构不仅有助于理解程序的内部工作原理,更能帮助开发人员编写出高效、稳定和易于维护的软件系统。
《Java数据结构和算法》(第2版)介绍了计算机编程中使用的数据结构和算法,对于在计算机应用中如何操作和管理数据以取得最优性能提供了深入浅出的讲解。全书共分为15章,分别讲述了基本概念、数组、简单排序、堆和...