本文目录一览：
双向循环链表java
我们也做这个，，你是是吧
package KeCheng1;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Iterator;
import java.util.Scanner;
//定义节点类
class NodeAnyType {
public AnyType data;
public NodeAnyType prev;
public NodeAnyType next;
public Node(AnyType d, NodeAnyType p, NodeAnyType n) {
data = d;
prev = p;
next = n;
}
}
public class MyLinkedListAnyType {
private int theSize;
private NodeAnyType beginMarker; //头标记或头节点
private NodeAnyType endMarker; //尾标记或尾节点
public MyLinkedList() {
beginMarker = new NodeAnyType(null, endMarker, endMarker);
endMarker = new NodeAnyType(null, beginMarker, beginMarker);
beginMarker.next = endMarker;
theSize = 0;
}
public int size() {
return theSize;
}
public boolean add(AnyType x) {
add(size(), x);
return true;
}
public void add(int idx, AnyType x) {
NodeAnyType p;
p = getNode(idx);
addBefore(p, x);
}
private NodeAnyType getNode(int idx) {
NodeAnyType p;
if (idx < 0 || idx > size()) {
throw new IndexOutOfBoundsException();
}
if (idx < size() / 2) {
p = beginMarker.next;
for (int i = 0; i < idx; i++) {
p = p.next;
}
} else {
p = endMarker;
for (int i = size(); i > idx; i--) {
p = p.prev;
}
}
return p;
}
private void addBefore(NodeAnyType p, AnyType x) {
NodeAnyType newNode = new NodeAnyType(x, p.prev, p);
newNode.prev.next = newNode;
p.prev = newNode;
theSize++;
}
public AnyType remove(int idx) {
return remove(getNode(idx));
}
private AnyType remove(NodeAnyType p) {
p.next.prev = p.prev;
p.prev.next = p.next;
theSize--;
return p.data;
}
public void print() { //输出链表
for (NodeAnyType x = beginMarker.next; x.next != beginMarker; x = x.next) {
System.out.print(x.data + " ");
}
System.out.print("\n");
}
public AnyType get(int idx) {
return getNode(idx).data;
}
public static void main(String[] args) {
MyLinkedList<Integer> La = new MyLinkedList<Integer>();
int Length;
Scanner sc = new Scanner(System.in);
System.out.println("请输入要创建的双向链表的长度：(大于6)");
Length = sc.nextInt();
System.out.println("请输入" + Length + "个元素创建La双向链表：");
for (int i = 0; i < Length; i++) {
La.add(sc.nextInt());
}
System.out.println("输入的原La双向链表：");
La.print();
System.out.println("在双向链表的第3个位置插入20:");
La.add(3, 20);
La.print();
System.out.println("删除第五位置上的数:");
La.remove(5);
La.print();
System.out.println("插入最后一个节点99:");
La.add(Length, 99);
La.print();
System.out.println("插入第一个节点0:");
La.add(0, 0);
La.print();
System.out.println("就地逆置:");
int M = Length + 2;
int b = 0;
for (Length = Length + 1; Length >= 0; Length--) {
int a = La.get(M - 1);
La.add(b, a);
b = b + 1;
La.remove(M);
}
La.print();
}
}
在Java中如何实现双向链表?
双向链表：就是有双向指针，即双向的链域。 链结点的结构：
┌────┬────┬────────┐
│ data │ next │ previous │
└────┴────┴────────┘
双向链表不必是双端链表（持有对最后一个链结点的引用），双端链表插入时是双向的。 有两条链：一条从头到尾，一条从尾到头，删除遍历时也是双向的。
/**
* 双向链表
*/
public class DoublyLinkedList<T> {
private Link<T> head; //首结点
private Link<T> rear; //尾部指针
public DoublyLinkedList() {
}
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);
if (isEmpty()) { //为空时，第1次插入的新结点为尾结点
rear = newLink;
} else {
head.previous = newLink; //旧头结点的上结点等于新结点
}
newLink.next = head; //新结点的下结点旧头结点
head = newLink; //赋值后，头结点的下结点是旧头结点，上结点null
}
public void insertLast(T data) { //在链尾 插入
Link<T> newLink = new Link<T>(data);
if (isEmpty()) {
head = newLink;
} else {
rear.next = newLink;
}
newLink.previous = rear;
rear = newLink; //赋值后，尾结点的上结点是旧尾结点，下结点null
}
public T deleteHead() { //删除 链头
if (isEmpty()) return null;
Link<T> temp = head;
head = head.next; //变更首结点，为下一结点
if (head != null) {
head.previous = null;
} else {
rear = null;
}
return temp.data;
}
public T deleteRear() { //删除 链尾
if (isEmpty()) return null;
Link<T> temp = rear;
rear = rear.previous; //变更尾结点，为上一结点
if (rear != null) {
rear.next = null;
} else {
head = null;
}
return temp.data;
}
public T find(T t) { //从头到尾find
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;
}
Link<T> current = head;
while (!current.data.equals(t)) {
current = current.next;
if (current == null) {
return null;
}
}
if (current == head) {
head = head.next;
if (head != null) {
head.previous = null;
}
} else if (current == rear) {
rear = rear.previous;
if (rear != null) {
rear.next = null;
}
} else {
//中间的非两端的结点，要移除current
current.next.previous = current.previous;
current.previous.next = current.next;
}
return current.data;
}
public boolean insertAfter(T key, T data) { //插入在key之后, key不存在return false
if (isEmpty()) {
return false;
}
Link<T> current = head;
while (!current.data.equals(key)) {
current = current.next;
if (current == null) {
return false;
}
}
Link<T> newLink = new Link<T>(data);
if (current == rear) {
rear = newLink;
} else {
newLink.next = current.next;
current.next.previous = newLink;
}
current.next = newLink;
newLink.previous = current;
return true;
}
public void displayList4Head() { //从头开始遍历
System.out.println("List (first--last):");
Link<T> current = head;
while (current != null) {
current.displayLink();
current = current.next;
}
}
public void displayList4Rear() { //从尾开始遍历
System.out.println("List (last--first):");
Link<T> current = rear;
while (current != null) {
current.displayLink();
current = current.previous;
}
}
class Link<T> { //链结点
T data; //数据域
Link<T> next; //后继指针，结点 链域
Link<T> previous; //前驱指针，结点 链域
Link(T data) {
this.data = data;
}
void displayLink() {
System.out.println("the data is " + data.toString());
}
}
public static void main(String[] args) {
DoublyLinkedList<Integer> list = new DoublyLinkedList<Integer>();
list.insertLast(1);
list.insertFirst(2);
list.insertLast(3);
list.insertFirst(4);
list.insertLast(5);
list.displayList4Head();
Integer deleteHead = list.deleteHead();
System.out.println("deleteHead:" + deleteHead);
list.displayList4Head();
Integer deleteRear = list.deleteRear();
System.out.println("deleteRear:" + deleteRear);
list.displayList4Rear();
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(1));
list.displayList4Head();
System.out.println("----在指定key后插入----");
list.insertAfter(2, 8);
list.insertAfter(2, 9);
list.insertAfter(9, 10);
list.displayList4Head();
}
}
java如何实现链表
链表是一种重要的数据结构，在程序设计中占有很重要的地位。C语言和C语言中是用指针来实现链表结构的，由于Java语言不提供指针，所以有人认为在Java语言中不能实现链表，其实不然，Java语言比C和C更容易实现链表结构。Java语言中的对象引用实际上是一个指针（本文中的指针均为概念上的意义，而非语言提供的数据类型），所以我们可以编写这样的类来实现链表中的结点。
class Node {
Object data;
Node next; //指向下一个结点
}
将数据域定义成Object类是因为Object类是广义超类，任何类对象都可以给其赋值，增加了代码的通用性。为了使链表可以被访问还需要定义一个表头，表头必须包含指向第一个结点的指针和指向当前结点的指针。为了便于在链表尾部增加结点，还可以增加一指向链表尾部的指针，另外还可以用一个域来表示链表的大小，当调用者想得到链表的大小时，不必遍历整个链表。 链表的数据结构 我们可以用类List来实现链表结构，用变量Head、Tail、Length、Pointer来实现表头。存储当前结点的指针时有一定的技巧，Pointer并非存储指向当前结点的指针，而是存储指向它的前趋结点的指针,当其值为null时表示当前结点是第一个结点。那么为什么要这样做呢？这是因为当删除当前结点后仍需保证剩下的结点构成链表，如果Pointer指向当前结点，则会给操作带来很大困难。那么如何得到当前结点呢，我们定义了一个方法cursor(),返回值是指向当前结点的指针。类List还定义了一些方法来实现对链表的基本操作，通过运用这些基本操作我们可以对链表进行各种操作。例如reset()方法使第一个结点成为当前结点。insert(Object d)方法在当前结点前插入一个结点，并使其成为当前结点。remove()方法删除当前结点同时返回其内容，并使其后继结点成为当前结点，如果删除的是最后一个结点，则第一个结点变为当前结点。 链表类List的源代码如下：
import java.io.*;
public class List {
/*用变量来实现表头*/
private Node Head = null;
private Node Tail = null;
private Node Pointer = null;
private int Length = 0;
public void deleteAll() {
/*清空整个链表*/
Head = null;
Tail = null;
Pointer = null;
Length = 0;
}
public void reset() {
/*链表复位，使第一个结点成为当前结点*/
Pointer = null;
}
public boolean isEmpty() {
/*判断链表是否为空*/
return (Length == 0);
}
public boolean isEnd() {
/*判断当前结点是否为最后一个结点*/
if (Length == 0)
throw new java.lang.NullPointerException();
else if (Length == 1)
return true;
else
return (cursor() == Tail);
}
public Object nextNode() {
/*返回当前结点的下一个结点的值，并使其成为当前结点*/
if (Length == 1)
throw new java.util.NoSuchElementException();
else if (Length == 0)
throw new java.lang.NullPointerException();
else {
Node temp = cursor();
Pointer = temp;
if (temp != Tail)
return (temp.next.data);
else
throw new java.util.NoSuchElementException();
}
}
public Object currentNode() {
/*返回当前结点的值*/
Node temp = cursor();
return temp.data;
}
public void insert(Object d) {
/*在当前结点前插入一个结点，并使其成为当前结点*/
Node e = new Node(d);
if (Length == 0) {
Tail = e;
Head = e;
} else {
Node temp = cursor();
e.next = temp;
if (Pointer == null)
Head = e;
else
Pointer.next = e;
}
Length++;
}
public int size() {
/*返回链表的大小*/
return (Length);
}
public Object remove() {
/*将当前结点移出链表，下一个结点成为当前结点，如果移出的结点是最后一个结点，则第一个结点成为当前结点*/
Object temp;
if (Length == 0)
throw new java.util.NoSuchElementException();
else if (Length == 1) {
temp = Head.data;
deleteAll();
} else {
Node cur = cursor();
temp = cur.data;
if (cur == Head)
Head = cur.next;
else if (cur == Tail) {
Pointer.next = null;
Tail = Pointer;
reset();
} else
Pointer.next = cur.next;
Length--;
}
return temp;
}
private Node cursor() {
/*返回当前结点的指针*/
if (Head == null)
throw new java.lang.NullPointerException();
else if (Pointer == null)
return Head;
else
return Pointer.next;
}
public static void main(String[] args) {
/*链表的简单应用举例*/
List a = new List();
for (int i = 1; i <= 10; i++)
a.insert(new Integer(i));
System.out.println(a.currentNode());
while (!a.isEnd())
System.out.println(a.nextNode());
a.reset();
while (!a.isEnd()) {
a.remove();
}
a.remove();
a.reset();
if (a.isEmpty())
System.out.println("There is no Node in List \n");
System.out.println("You can press return to quit\n");
try {
System.in.read();
//确保用户看清程序运行结果
} catch (IOException e) {
}
}
}
class Node {
/*构成链表的结点定义*/
Object data;
Node next;
Node(Object d) {
data = d;
next = null;
}
}
读者还可以根据实际需要定义新的方法来对链表进行操作。双向链表可以用类似的方法实现只是结点的类增加了一个指向前趋结点的指针。 可以用这样的代码来实现：
class Node {
Object data;
Node next;
Node previous;
Node(Object d) {
data = d;
next = null;
previous = null;
}
}
当然，双向链表基本操作的实现略有不同。链表和双向链表的实现方法，也可以用在堆栈和队列的实现中，这里就不再多写了，有兴趣的读者可以将List类的代码稍加改动即可。 希望对你有帮助。
Java语言没有指针，怎样实现链表?
Java语言中的对象引用实际上是一个指针（这里的指针均为概念上的意义，而非语言提供的数据类型），所以我们可以编写这样的类来实现链表中的结点。 程序代码：
class Node {
Object data;
Node next; //指向下一个结点
}
将数据域定义成Object类是因为Object类是广义超类，任何类对象都可以给其赋值，增加了代码的通用性。为了使链表可以被访问还需要定义一个表头，表头必须包含指向第一个结点的指针和指向当前结点的指针。为了便于在链表尾部增加结点，还可以增加一指向链表尾部的指针，另外还可以用一个域来表示链表的大小，当调用者想得到链表的大小时，不必遍历整个链表。 链表的数据结构我们可以用类List来实现链表结构，用变量Head、Tail、Length、Pointer来实现表头。存储当前结点的指针时有一定的技巧，Pointer并非存储指向当前结点的指针，而是存储指向它的前趋结点的指针,当其值为null时表示当前结点是第一个结点，因为当删除当前结点后仍需保证剩下的结点构成链表，如果Pointer指向当前结点，则会给操作带来很大困难。如何得到当前结点呢？我们定义了一个方法cursor(),返回值是指向当前结点的指针。类List还定义了一些方法来实现对链表的基本操作，通过运用这些基本操作我们可以对链表进行各种操作。例如reset()方法使第一个结点成为当前结点。insert(Object d)方法在当前结点前插入一个结点，并使其成为当前结点。remove()方法删除当前结点同时返回其内容，并使其后继结点成为当前结点，如果删除的是最后一个结点，则第一个结点变为当前结点。 链表类List的源代码如下：
package cn.javatx;
import java.io.IOException;
public class List {
private Node Head = null;
private Node Tail = null;
private Node Pointer = null;
private int Length = 0;
public void deleteAll() {
Head = null;
Tail = null;
Pointer = null;
Length = 0;
}
public void reset() {
Pointer = null;
}
public boolean isEmpty() {
return (Length == 0);
}
public boolean isEnd() {
if (Length == 0)
throw new java.lang.NullPointerException();
else if (Length == 1)
return true;
else
return (cursor() == Tail);
}
public Object nextNode() {
if (Length == 1)
throw new java.util.NoSuchElementException();
else if (Length == 0)
throw new java.lang.NullPointerException();
else {
Node temp = cursor();
Pointer = temp;
if (temp != Tail)
return (temp.next.data);
else
throw new java.util.NoSuchElementException();
}
}
public Object currentNode() {
Node temp = cursor();
return temp.data;
}
public void insert(Object d) {
Node e = new Node(d);
if (Length == 0) {
Tail = e;
Head = e;
} else {
Node temp = cursor();
e.next = temp;
if (Pointer == null)
Head = e;
else
Pointer.next = e;
}
Length++;
}
public int size() {
return (Length);
}
public Object remove() {
Object temp;
if (Length == 0)
throw new java.util.NoSuchElementException();
else if (Length == 1) {
temp = Head.data;
deleteAll();
} else {
Node cur = cursor();
temp = cur.data;
if (cur == Head)
Head = cur.next;
else if (cur == Tail) {
Pointer.next = null;
Tail = Pointer;
reset();
} else
Pointer.next = cur.next;
Length--;
}
return temp;
}
private Node cursor() {
if (Head == null)
throw new java.lang.NullPointerException();
else if (Pointer == null)
return Head;
else
return Pointer.next;
}
public static void main(String[] args) {
List a = new List();
for (int i = 1; i <= 10; i++)
a.insert(new Integer(i));
System.out.println(a.currentNode());
while (!a.isEnd())
System.out.println(a.nextNode());
a.reset();
while (!a.isEnd()) {
a.remove();
}
a.remove();
a.reset();
if (a.isEmpty())
System.out.println("There is no Node in List \n");
System.out.println("You can press return to quit\n");
try {
System.in.read();
} catch (IOException e) {
}
}
}
class Node {
Object data;
Node next;
Node(Object d) {
data = d;
next = null;
}
}
当然，双向链表基本操作的实现略有不同。链表和双向链表的实现方法，也可以用在堆栈和队列的现实中。
