① 在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语言，编写一个链表类(双向链表),实现插入,删除,查找操作。新手，要俗易懂些，最好自己调适通过。急
定义接口：
//Deque.java
package dsa; //根据自己的程序位置不同
public interface Deque {
public int getSize();//返回队列中元素数目
public boolean isEmpty();//判断队列是否为空
public Object first() throws ExceptionQueueEmpty;//取首元素（但不删除）
public Object last() throws ExceptionQueueEmpty;//取末元素（但不删除）
public void insertFirst(Object obj);//将新元素作为首元素插入
public void insertLast(Object obj);//将新元素作为末元素插入
public Object removeFirst() throws ExceptionQueueEmpty;//删除首元素
public Object removeLast() throws ExceptionQueueEmpty;//删除末元素
public void Traversal();//遍历
}
双向链表实现：
//Deque_DLNode.java
/*
* 基于双向链表实现双端队列结构
*/
package dsa;
public class Deque_DLNode implements Deque {
protected DLNode header;//指向头节点（哨兵）
protected DLNode trailer;//指向尾节点（哨兵）
protected int size;//队列中元素的数目
//构造函数
public Deque_DLNode() {
header = new DLNode();
trailer = new DLNode();
header.setNext(trailer);
trailer.setPrev(header);
size = 0;
}
//返回队列中元素数目
public int getSize()
{ return size; }
//判断队列是否为空
public boolean isEmpty()
{ return (0 == size) ? true : false; }
//取首元素（但不删除）
public Object first() throws ExceptionQueueEmpty {
if (isEmpty())
throw new ExceptionQueueEmpty("意外：双端队列为空");
return header.getNext().getElem();
}
//取末元素（但不删除）
public Object last() throws ExceptionQueueEmpty {
if (isEmpty())
throw new ExceptionQueueEmpty("意外：双端队列为空");
return trailer.getPrev().getElem();
}
//在队列前端插入新节点
public void insertFirst(Object obj) {
DLNode second = header.getNext();
DLNode first = new DLNode(obj, header, second);
second.setPrev(first);
header.setNext(first);
size++;
}
//在队列后端插入新节点
public void insertLast(Object obj) {
DLNode second = trailer.getPrev();
DLNode first = new DLNode(obj, second, trailer);
second.setNext(first);
trailer.setPrev(first);
size++;
}
//删除首节点
public Object removeFirst() throws ExceptionQueueEmpty {
if (isEmpty())
throw new ExceptionQueueEmpty("意外：双端队列为空");
DLNode first = header.getNext();
DLNode second = first.getNext();
Object obj = first.getElem();
header.setNext(second);
second.setPrev(header);
size--;
return(obj);
}
//删除末节点
public Object removeLast() throws ExceptionQueueEmpty {
if (isEmpty())
throw new ExceptionQueueEmpty("意外：双端队列为空");
DLNode first = trailer.getPrev();
DLNode second = first.getPrev();
Object obj = first.getElem();
trailer.setPrev(second);
second.setNext(trailer);
size--;
return(obj);
}
//遍历
public void Traversal() {
DLNode p = header.getNext();
while (p != trailer) {
System.out.print(p.getElem()+" ");
p = p.getNext();
}
System.out.println();
}
}
③ 谁能帮我把这Java单向链表改成双向链表
一、JAVA单向链表的操作（增加节点、查找节点、删除节点）
classLink{//链表类
classNode{//保存每一个节点，此处为了方便直接定义成内部类
privateStringdata;//节点的内容
privateNodenext;//保存下一个节点
publicNode(Stringdata){//通过构造方法设置节点内容
this.data=data;
}
publicvoidadd(Nodenode){//增加节点
if(this.next==null){//如果下一个节点为空，则把新节点加入到next的位置上
this.next=node;
}else{//如果下一个节点不为空，则继续找next
this.next.add(node);
}
}
publicvoidprint(){//打印节点
if(this.next!=null){
System.out.print(this.data+"-->");
this.next.print();
}else{
System.out.print(this.data+"
");
}
}
publicbooleansearch(Stringdata){//内部搜索节点的方法
if(this.data.equals(data)){
returntrue;
}
if(this.next!=null){
returnthis.next.search(data);
}else{
returnfalse;
}
}
publicvoiddelete(Nodeprevious,Stringdata){//内部删除节点的方法
if(this.data.equals(data)){
previous.next=this.next;
}else{
if(this.next!=null){
this.next.delete(this,data);
}
}
}
}
privateNoderoot;//定义头节点
publicvoidaddNode(Stringdata){//根据内容添加节点
NodenewNode=newNode(data);//要插入的节点
if(this.root==null){//没有头节点，则要插入的节点为头节点
this.root=newNode;
}else{//如果有头节点，则调用节点类的方法自动增加
this.root.add(newNode);
}
}
publicvoidprint(){//展示列表的方法
if(root!=null){//当链表存在节点的时候进行展示
this.root.print();
}
}
publicbooleansearchNode(Stringdata){//在链表中寻找指定内容的节点
returnroot.search(data);//调用内部搜索节点的方法
}
publicvoiddeleteNode(Stringdata){//在链表中删除指定内容的节点
if(root.data.equals(data)){//如果是头节点
if(root.next!=null){
root=root.next;
}else{
root=null;
}
}else{
root.next.delete(this.root,data);
}
}
}二、双向链表的简单实现
publicclassDoubleLink<T>{
/**
*Node<AnyType>类定义了双向链表中节点的结构，它是一个私有类，而其属性和构造函数都是公有的，这样，其父类可以直接访问其属性
*而外部类根本不知道Node类的存在。
*
*@authorZHB
*
*@param<T>
*类型
*@paramData
*是节点中的数据
*@parampre
*指向前一个Node节点
*@paramnext
*指向后一个Node节点
*/
privateclassNode<T>{
publicNode<T>pre;
publicNode<T>next;
publicTdata;
publicNode(Tdata,Node<T>pre,Node<T>next){
this.data=data;
this.pre=pre;
this.next=next;
}
publicNode(){
this.data=null;
this.pre=null;
this.next=null;
}
}
//下面是DoubleLinkedList类的数据成员和方法
privateinttheSize;
privateNode<T>Header;
privateNode<T>Tail;
/*
*构造函数我们构造了一个带有头、尾节点的双向链表头节点的Next指向尾节点为节点的pre指向头节点链表长度起始为0。
*/
publicDoubleLink(){
theSize=0;
Header=newNode<T>(null,null,null);
Tail=newNode<T>(null,Header,null);
Header.next=Tail;
}
publicvoidadd(Titem){
Node<T>aNode=newNode<T>(item,null,null);
Tail.pre.next=aNode;
aNode.pre=Tail.pre;
aNode.next=Tail;
Tail.pre=aNode;
theSize++;
}
publicbooleanisEmpty(){
return(this.theSize==0);
}
publicintsize(){
returnthis.theSize;
}
publicTgetInt(intindex){
if(index>this.theSize-1||index<0)
();
Node<T>current=Header.next;
for(inti=0;i<index;i++){
current=current.next;
}
returncurrent.data;
}
publicvoidprint(){
Node<T>current=Header.next;
while(current.next!=null){
System.out.println(current.data.toString());
current=current.next;
}
}
publicstaticvoidmain(String[]args){
DoubleLink<String>dLink=newDoubleLink<String>();
dLink.add("zhb");
dLink.add("zzb");
dLink.add("zmy");
dLink.add("zzj");
System.out.println("size:"+dLink.size());
System.out.println("isEmpty?:"+dLink.isEmpty());
System.out.println("3:"+dLink.getInt(2));
dLink.print();
}
}
④ JAVA中LinkedList的底层实现是链表还是队列
是链表实现，通过引用来找到前面或后面的对象，所以相对来说LinkedList插入、删除操作比较快，查找较慢，是双向链表。
⑤ java单线链表、双向链表及循环链表中插入某节点,和删除某节点的算法（可能是头结点、中间节点、尾节点）
API里有现成的，直接用好了
java.util.List
remove
E remove(int index)移除列表中指定位置的元素（可选操作）。将所有的后续元素向左移动（将其索引减 1）。返回从列表中移除的元素。
参数：
index - 要移除的元素的索引
返回：
以前在指定位置的元素
抛出：
UnsupportedOperationException - 如果列表不支持 remove 操作
IndexOutOfBoundsException - 如果索引超出范围 (index < 0 || index >= size())
remove
boolean remove(Object o)从此列表中移除第一次出现的指定元素（如果存在）（可选操作）。如果列表不包含元素，则不更改列表。更确切地讲，移除满足 (o==null ? get(i)==null : o.equals(get(i))) 的最低索引 i 的元素（如果存在这样的元素）。如果此列表已包含指定元素（或者此列表由于调用而发生更改），则返回 true。
指定者：
接口 Collection<E> 中的 remove
参数：
o - 要从该列表中移除的元素，如果存在的话
返回：
如果列表包含指定的元素，则返回 true
抛出：
ClassCastException - 如果指定元素的类型和此列表不兼容（可选）
NullPointerException - 如果指定的元素是 null，并且此列表不允许 null 元素（可选）
UnsupportedOperationException - 如果列表不支持 remove 操作
⑥ java怎么用链表实现
在数据结构中经常看见的一个基本概念-链表。
链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。
在Java中，对于链表的实现都是基于引用数据类型操作的。实现大致如下：
定义节点类Node，节点的概念很重要，一个链表是由各各节点连接在一起组成的。在节点类Node中定义节点内容及指向下一节点的引用，再增加一个添加节点的方法即可完成链表实现。
链表有很多种不同的类型：单向链表，双向链表以及循环链表。在执行效率上，相比数组而言，链表插入快查找慢，开发中得根据实际业务使用。
⑦ 用java如何创建一个单链表和双链表
单向链表
单向链表就是通过每个结点的指针指向下一个结点从而链接起来的结构。
单向链表的初始化：这里我所讲的链表都是头结点不参与计算的，也就是说第一个结点都是头结点后面的第一个结点。所以我要先申明一点，这里我把链表的初始化放在了构造函数部分，然后析构函数负责释放头结点的内存。
单向链表的创建过程：链表的创建就是添加结点到链表的最后，开始是添加一个结点到head结点后面，然后添加一个结点到上次添加的结点后面，每次新建的结点的指针总是指向NULL指针。从上面的示意图可以看出，我们需要一个辅助指针一直指向最后一个结点，这个辅助结点就是为了让每次添加的结点都放置在最后一个位置。
单向链表插入结点过程：源代码中的的插入结点函数我设置了一个指定位置，就是在指定位置插入结点。首先，通过位置变量position让ptemp结点移动到要插入位置的前一个位置，然后接下来的过程就是和创建链表的过程是一样的，把新建的结点添加到ptemp的后面。这里变量position可以从1到链表长度加1，意思就是如果不算头结点的话有3个结点，那你的position变量就可以从1到4，这是因为ptemp指针可以到第3个结点的位置，所以新建结点的位置就可以到4了。
单向链表删除结点过程：源代码中的删除结点函数也有一个指定位置变量，为了删除指定位置的结点。和插入结点一样通过变量position把ptemp移动到要删除结点的前一个位置，然后让ptemp结点中的指针指向要删除结点后面的一个结点，也就是ptemp结点的下一个的下一个结点，虽然这个结点可能为空，但是程序还是正常运行。但是这里和插入结点不同的是变量position只能从1到链表的长度，是因为ptemp移动到最后一个结点的时候，它的下一个结点为空，所以不不需要参与删除了。
双向链表
1.听名字可能就能猜到双向链表就是链表结点包含两个指针，一个指针是指向下一个结点的，另一个指针当然就是指向上一个结点的。
2.双向链表的初始化：由于这里的链表头结点不参与计算，所以头结点的pPre指针是一直指向NULL指针的。
3.双向链表的创建过程：由于双向链表的每个结点包含两个指针那么这个时候我们就要小心处理好每一个指针的指向，要不然会有很多意想不到的错误。同样的，和单向链表的创建过程一样，需要一个辅助指针来指向最后一个结点，然后每新建一个结点，这个结点的pNext指针都是指向NULL指针的，pPre指针指向上一个结点（这是和单向链表不同的地方），然后让上一个指针的pNext指向新建的结点，这样整个链表就连接起来了。
4.双向链表插入结点过程：知道了双向链表的创建过程，那么插入结点的过程就大同小异 了，有一点需要特别注意的就是这里的变量position范围也是从1到链表长度加1，但是如果待插入的位置是最后一个位置的话，情况就不同了，看到下面的图我们可以很好的理解，因为没新建一个结点的时候都需要处理两个指针，而且新建结点的下一个结点的pPre指针就需要指向这个新建的结点，但是有可能这个新建的结点可能就已经是最后一个结点了，那么这个时候再执行
ptemp->pNext->pPre=pnew;
这条指令的时候就会报错了，因为ptemp->pNext已经是个NULL指针了，那空指针哪里还有pPre呢。因此在程序中要进行一次判断，看看结点是否是最后一个结点。
5.双向链表删除结点的过程：要注意的问题和插入结点一样，看看这个结点是否为NULL。这里就不重复了。