「java链表案例」java中链表的实现

本篇文章给大家谈谈java链表案例，以及java中链表的实现对应的知识点，希望对各位有所帮助，不要忘了收藏本站喔。

本文目录一览：

• 1、用Java语言实现单向链表
• 2、用JAVA语言解决：编写一个链表类(双向链表),实现插入,删除,查找操作
• 3、写一个java链表的例子？随便举例说一下。
• 4、Java合并两个排序的链表问题（剑指offer）
• 5、java 链表
• 6、. java怎么创建链表

用Java语言实现单向链表

1.先定义一个节点类

package com.buren;

public class IntNode {

//定义一个节点类

int

info;

//定义属性，节点中的值

IntNode next;

//定义指向下一个节点的属性

public IntNode(int

i){ //构造一个next为空的节点

this(i,null);

}

public IntNode(int i,IntNode

n){ //构造值为i指向n的节点

info=i;

next=n;

}

}

2.再定义一个链表类，这是主要部分

package com.buren;

public class IntSLList {

private IntNode head,tail;

//定义指向头结点和尾结点的指针，

//如果大家看着这个不像指针的话，那就需要对指针有更深刻的了解

public

IntSLList(){

//定义一个空节点

head=tail=null;

}

public boolean

isEmpty(){

//判断节点是否为空

return

head==null;

//这行代码看起来似乎很神奇，其实真的很神奇，偶是服了

}

public void addToHead(int el){

//将el插入到头结点前

head=new

IntNode(el,head);

//将节点插入到头结点前，作为新的投节点

if(head==tail){

//给空链表插入节点时

tail=head;

//头结点和尾结点指向同一个节点

}

}

public void addToTail(int

el){

//向链表的尾部增加结点

if(!isEmpty()){

//判断链表是否为空

tail.next=new

IntNode(el);

//新建立一个值为el的节点，将链表的尾结点指向新节点

tail=tail.next;

//更新尾指针的指向

}else{

head=tail=new

IntNode(el);

//如果链表为空，新建立一个节点，将头尾指针同时指向这个节点

}

}

public int

deleteFromHead(){

//删除头结点，将节点信息返回

int

el=head.info;

//取出节点信息

if(head==tail){

//如果链表中只有一个节点

head=tail=null;

//删除这一个节点

}else{

head=head.next;

//如果链表中不止一个节点，将头结点的下一个节点作为头结点

}

return

el;

//返回原头结点的值

}

public int

deleteFromTail(){

//删除尾结点，返回尾结点的信息

int

el=tail.info;

//取出尾结点的值

if(head==tail){

// 如果链表中只有一个节点

head=tail=null;

//删除这个节点

}else{

IntNode

temp;

//定义中间变量

for(temp=head;temp.next!=tail;temp=temp.next);

//找出尾结点的前一个节点，注意最后的分号，

//这个for循环是没有循环体的，目的在于找出尾结点的前一个节点

//在整个程序中用了很多次这样的写法，相当经典啊

tail=temp;

//将找出来的节点作为尾结点，删除原来的尾结点

tail.next=null;

//将新尾结点的指向设为空

}

return

el;

//返回原尾结点的信息

}

public void

printAll(){

//打印链表中所有节点的信息

if(isEmpty()){

//如果链表为空

System.out.println("This

list is

empty!");

//输出提示信息

return;

//返回到调用的地方

}

if(head==tail){

//当链表中只有一个节点时

System.out.println(head.info);

//输出这个节点的信息，就是头结点的信息

return;

}

IntNode

temp;

//定义一个中间变量

for(temp=head;temp!=null;temp=temp.next){

//遍历整个链表

System.out.print(temp.info+"

");

//输出每个节点的信息

}

System.out.println();

//输出一个换行，可以没有这一行

}

public boolean isInList(int

el){

//判断el是否存在于链表中

IntNode

temp;

//定义一个中间变量

for(temp=head;temp!=null

temp.info!=el;temp=temp.next);

//将el找出来，注意最后的分

return

temp!=null;

// 如果存在返回true，否则返回flase，这两行代码很有思想

}

public void delete(int

el){

//删除链表中值为el的节点

if(head.info==el

head==tail){

//如果只有一个节点，并且节点的值为el

head=tail=null;

//删除这个节点

}else

if(head.info==el){

// 不止一个节点，而头结点的值就是el

head=head.next;

//删除头结点

}else{

IntNode

pred,temp;

//定义两个中间变量

for(pred=head,temp=head.next;temp.info!=el

temp.next!=null;pred=pred.next,temp=temp.next);

//跟上面的类似，自己琢磨吧，也是要注意最后的分号

pred.next=temp.next;

//将temp指向的节点删除，最好画一个链表的图，有助于理解

if(temp==tail){

//如果temp指向的节点是尾结点

tail=pred;

//将pred指向的节点设为尾结点，

}

}

}

//下面这个方法是在链表中值为el1的节点前面插入一个值为el2的节点，

//用类似的思想可以再写一个在链表中值为el1的节点后面插入一个值为el2的节点

public boolean insertToList(int el1,int

el2){

//定义一个插入节点的方法，插入成功返回true，否则返回false

IntNode

pred,temp; //定义两个中间变量

if(isEmpty()){

//判断链表是否为空

return

false;

//如果链表为空就直接返回false

}

if(head.info==el1

head==tail){

//如果链表中只有一个节点，并且这个节点的值是el1

head=new

IntNode(el2,head);

//新建立一个节点

return

true;

}else if(head.info==el1){

IntNode t=new

IntNode(el2);

t.next=head;

head=t;

return

true;

}else{

for(pred=head,temp=head.next;temp!=null

temp.info!=el1;pred=pred.next,temp=temp.next);

if(temp!=null){

IntNode

a=new IntNode(el2);

pred.next=a;

a.next=temp;

return

true;

}else{

System.out.println(el1+"

NOT EXEISTS!");

return

false;

}

}

}

3.下面是测试代码

public static void main(String[] args){

IntSLList test=new

IntSLList();

//test.addToHead(7);

test.addToTail(7);

System.out.println(test.insertToList(7,5));

test.printAll();

System.out.println(test.isInList(123));

}

}

用JAVA语言解决：编写一个链表类(双向链表),实现插入,删除,查找操作

public class DoubleLinkedList

{

// 节点类Node

private static class Node

{

Object value;

Node prev = this;

Node next = this;

Node(Object v)

{

value = v;

}

public String toString()

{

return value.toString();

}

}

private Node head = new Node(null); // 头节点

private int size; // 链表大小

// 以下是接口方法

public boolean addFirst(Object o)

{

addAfter(new Node(o), head);

return true;

}

public boolean addLast(Object o)

{

addBefore(new Node(o), head);

return true;

}

public boolean add(Object o)

{

return addLast(o);

}

public boolean add(int index, Object o)

{

addBefore(new Node(o), getNode(index));

return true;

}

public boolean remove(int index)

{

removeNode(getNode(index));

return true;

}

public boolean removeFirst()

{

removeNode(head.next);

return true;

}

public boolean removeLast()

{

removeNode(head.prev);

return true;

}

public Object get(int index)

{

return getNode(index).value;

}

public int size()

{

return size;

}

public String toString()

{

StringBuffer s = new StringBuffer("[");

Node node = head;

for (int i = 0; i size; i++)

{

node = node.next;

if (i 0)

s.append(", ");

s.append(node.value);

}

s.append("]");

return s.toString();

}

private Node getNode(int index)

{

if (index 0 || index = size)

throw new IndexOutOfBoundsException();

Node node = head.next;

for (int i = 0; i index; i++)

node = node.next;

return node;

}

private void addBefore(Node newNode, Node node)

{

newNode.next = node;

newNode.prev = node.prev;

newNode.next.prev = newNode;

newNode.prev.next = newNode;

size++;

}

private void addAfter(Node newNode, Node node)

{

newNode.prev = node;

newNode.next = node.next;

newNode.next.prev = newNode;

newNode.prev.next = newNode;

size++;

}

private void removeNode(Node node)

{

node.prev.next = node.next;

node.next.prev = node.prev;

node.prev = null;

node.next = null;

size--;

}

}

//测试类：

public class Test

{

public static void main(String[] args)

{

DoubleLinkedList dll = new DoubleLinkedList();

//添加

dll.add("张三");

dll.add("李四");

dll.add("王五");

System.out.println(dll);

//添加到最前

dll.addFirst("孙七");

System.out.println(dll);

//添加到最后，同添加

dll.addLast("赵六");

System.out.println(dll);

//添加到指定位置

dll.add(4, "王祖贤");

System.out.println(dll);

//移除最前的

dll.removeFirst();

System.out.println(dll);

//移除最后的

dll.removeLast();

System.out.println(dll);

//移除指定位置上的

dll.remove(2);

System.out.println(dll);

//返回指定位置上的元素

System.out.println(dll.get(1));

}

}

写一个java链表的例子？随便举例说一下。

//单链表类

package dataStructure.linearList;

import dataStructure.linearList.Node; //导入单链表结点类

import java.util.Iterator; //导入迭代器接口

public class SinglyLinkedListE extends AbstractListE implements LListE //单链表类，实现线性表接口

{

protected NodeE head; //头指针，指向单链表第1个结点

public SinglyLinkedList() //构造空单链表

{

this.head = null;

}

public SinglyLinkedList(NodeE head) //构造指定头指针的单链表

{

this.head = head;

}

public boolean isEmpty() //判断单链表是否为空，O(1)

{

return this.head==null;

}

public int length() //返回单链表长度

{ //单链表遍历算法，O(n)

int i=0;

NodeE p=this.head;

while (p!=null)

{

i++;

p = p.next;

}

return i;

}

public E get(int index) //返回序号为index的对象，index初值为0

{ //若单链表空或序号错误返回null，O(n)

if (this.head!=null index=0)

{

int j=0;

NodeE p=this.head;

while (p!=null jindex)

{

j++;

p = p.next;

}

if (p!=null)

return (E)p.data;

}

return null;

}

public E set(int index, E element) //设置序号为index的对象为element，O(n)

{ //若操作成功返回原对象，否则返回null

if (this.head!=null index=0 element!=null)

{

int j=0;

NodeE p=this.head;

while (p!=null jindex)

{

j++;

p = p.next;

}

if (p!=null)

{

E old = (E)p.data;

p.data = element;

return old; //若操作成功返回原对象

}

}

return null; //操作不成功

}

public boolean add(int index, E element) //插入element对象，插入后对象序号为index

{ //若操作成功返回true，O(n)

if (element==null)

return false; //不能添加空对象（null）

if (this.head==null || index=0) //头插入

this.head = new NodeE(element, this.head);

else //单链表不空且index=1

{

int j=0;

NodeE p=this.head;

while (p.next!=null jindex-1) //寻找插入位置

{

j++;

p = p.next;

}

p.next = new NodeE(element, p.next);//中间/尾插入

}

return true;

}

public boolean add(E element) //在单链表最后添加对象，重载，O(n)

{

return add(Integer.MAX_VALUE, element);

}

public E remove(int index) //移去序号为index的对象，O(n)

{ //若操作成功返回被移去对象，否则返回null

E old = null;

if (this.head!=null index=0)

if (index==0) //头删除

{

old = (E)this.head.data;

this.head = this.head.next;

}

else //中间/尾删除

{

int j=0;

NodeE p=this.head;

while (p.next!=null jindex-1) //定位到待删除结点的前驱结点

{

j++;

p = p.next;

}

if (p.next!=null)

{

old = (E)p.next.data; //操作成功，返回原对象

p.next = p.next.next; //删除p的后继结点

}

}

return old;

}

public void clear() //清空单链表，O(1)

{

this.head = null;

}

public String toString() //返回显示单链表所有元素值对应的字符串

{ //单链表遍历算法，O(n)

String str="(";

NodeE p = this.head;

while (p!=null)

{

str += p.data.toString();

p = p.next;

if (p!=null)

str += ", ";

}

return str+")";

}

//以上实现LList接口，第2章

//以下2.4 迭代器内容

public IteratorE iterator() //返回一个迭代器对象

{

return new Itr();

}

private class Itr implements IteratorE //私有内部类，实现迭代器接口

{

private NodeE cursor = head;

public boolean hasNext() //若有后继元素，返回true

{

return cursor!=null cursor.next!=null;

}

public E next() //返回后继元素

{

if (cursor != null cursor.next!=null)

{

E element = cursor.next.data;

cursor = cursor.next;

return element;

}

return null;

}

public void remove() //不支持该操作

{

throw new UnsupportedOperationException();

}

}//内部类Itr结束

//以下第8章 8.2.1 顺序查找，散列表中用

public NodeE search(E element, NodeE start) //从单链表结点start开始顺序查找指定对象

{ //若查找成功返回结点，否则返回null

if (this.head==null || element==null)

return null;

NodeE p=start;

while (p!=null !element.equals(p.data))

{

System.out.print(p.data+"? ");

p = p.next;

}

return p;

}

public NodeE search(E element) //顺序查找指定对象

{

return search(element, head);

}

/*

public boolean contain(E element) //以查找结果判断单链表是否包含指定对象

{ //若包含返回true，否则返回false

return this.search(element)!=null;

}

*/

public boolean remove(E element) //移去首次出现的指定对象，O(n)

{ //若操作成功返回true

if (this.head==null || element==null)

return false;

if (element.equals(this.head.data))

{

this.head = this.head.next; //头删除

return true;

}

NodeE front=this.head, p=front.next; //中间/尾删除

while (p!=null !element.equals(p.data))

{

front = p;

p=p.next;

}

if (p!=null)

{

front.next = p.next;

return true;

}

return false;

}

//以下是第2章习题

public SinglyLinkedList(E[] element) //由指定数组中的多个对象构造单链表

{

this.head = null;

if (element!=null element.length0)

{

this.head = new Node(element[0]);

NodeE rear=this.head;

int i=1;

while (ielement.length)

{

rear.next = new Node(element[i++]);

rear = rear.next;

}

}

}

public void concat(SinglyLinkedList list) //将指定单链表list链接在当前单链表之后

{

if (this.head==null)

this.head = list.head;

else

{

NodeE p=this.head;

while (p.next!=null)

p = p.next;

p.next = list.head;

}

}

public SinglyLinkedList(SinglyLinkedListE list) //以单链表list构造新的单链表

{ //复制单链表

this.head = null;

if (list!=null list.head!=null)

{

this.head = new Node(list.head.data);

NodeE p = list.head.next;

NodeE rear = this.head;

while (p!=null)

{

rear.next = new NodeE(p.data);

rear = rear.next;

p = p.next;

}

}

}

//递归方法

// public SinglyLinkedList(SinglyLinkedListE list) //以单链表list构造新的单链表

public void copy(SinglyLinkedListE list) //复制单链表

{

this.head = copy(list.head);

}

private NodeE copy(NodeE p) //复制单链表，递归方法

{

NodeE q=null;

if (p!=null)

{

q = new Node(p.data);

q.next = copy(p.next);

}

return q;

}

/*//递归方法

public String toString()

{

return "("+ this.toString(this.head) +")";

}

public String toString(NodeE p) //递归方法

{

if (p!=null)

return p.data.toString() + ", " + this.toString(p.next); //递归调用

return "";

}

public SinglyLinkedList(E[] element) //由指定数组中的多个对象构造单链表

{

this.head = null;

if (element!=null)

this.head = create(element,0);

}

private NodeE create(E[] element, int i) //由指定数组构造单链表

{ //递归方法

NodeE p=null;

if (ielement.length)

{

p = new Node(element[i]);

p.next = create(element, i+1);

}

return p;

}

*/

public boolean equals(Object obj) //比较两条单链表是否相等

{

if (obj == this)

return true;

if (obj instanceof SinglyLinkedList)

{

SinglyLinkedList list = (SinglyLinkedList)obj;

return equals(this.head, list.head);

}

return false;

}

private boolean equals(NodeE p, NodeE q) //比较两条单链表是否相等，递归方法

{

if (p==null q==null)

return true;

if (p!=null q!=null)

return p.data.equals(q.data) equals(p.next, q.next);

return false;

}

//以下是第8章习题

public boolean replace(Object obj, E element)//将元素值为obj的结点值替换为element，O(n)

{ //若替换成功返回true，否则返回false

if (obj==null || element==null)

return false;

NodeE p=this.head;

while (p!=null)

{

if (obj.equals(p.data))

{

p.data = element;

return true;

}

p = p.next;

}

return false;

}

public boolean replaceAll(Object obj, E element) //将所有元素值为obj的结点值替换为element，O(n)

{ //若替换成功返回true，否则返回false

boolean done=false;

if (obj!=null element!=null)

{

NodeE p=this.head;

while (p!=null)

{

if (obj.equals(p.data))

{

p.data = element;

done = true;

}

p = p.next;

}

}

return done;

}

public boolean removeAll(Object obj) //将所有元素值为obj的结点删除

{

if (this.head==null || obj==null)

return false;

boolean done=false;

while (this.head!=null obj.equals(this.head.data))

{

this.head = this.head.next; //头删除

done = true;

}

NodeE front=this.head, p=front.next;

while(p!=null)

{

if (obj.equals(p.data))

{

front.next = p.next; //删除p结点

p = front.next;

done = true;

}

else

{

front = p;

p = p.next;

}

}

return done;

}

public static void main(String[] args)

{

String[] letters={"A","B","C","D","E","F"};

SinglyLinkedListString list1 = new SinglyLinkedListString(letters);

SinglyLinkedListString list2 = new SinglyLinkedListString(list1);

list2.copy(list1);

System.out.println(list2.toString());

System.out.println("equals()， "+list2.equals(list1));

}

}

/*

程序运行结果如下：

(A, B, C, D, E, F)

*/

/* 第2章 //可行，但效率低，时间复杂度是O(n*n)。

public String toString()

{

String str="{";

if (this.length()!=0)

{

for(int i=0; ithis.length()-1; i++)

str += this.get(i).toString()+", ";

str += this.get(this.length()-1).toString();

}

return str+"}";

}

*/

Java合并两个排序的链表问题（剑指offer）

1、先将两个链表分别进行各自排序。如果题目已说明原来的两个链表是已经排好序的话，此步可以省略。

2、新建一个空链表，按照顺序（或者由小到大或者由大到小），依次将两个链表的数据排列到新的链表中。

这样最后得到的链表就是最终合并的链表。

java 链表

public class NodeT {

public T value;

public NodeT next;

public Node(T value, NodeT next) {

this.value = value;

this.next = next;

}

}

public class EverySecond {

public T NodeT everySecond(NodeT list) {

NodeT tmp = new NodeT(list.value, null);

if (list.next != null) {

tmp.next = everySecond(list.next);

}

return tmp;

}

}

public class EverySecondDriver {

public static void main(String[] args) {

// Build list

char[] values = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};

NodeCharacter list = null;

for (int i = values.length - 1; i = 0; i--) {

list = new NodeCharacter(values[i], list);

}

// Print list

System.out.print("List:" + list);

for (NodeCharacter n = list; n != null; n = n.next) {

System.out.print(" " + n.value);

}

System.out.println();

// Get new list, with every second element

EverySecond es = new EverySecond();

NodeCharacter result = es.everySecond(list);

// Print result

System.out.print("Result:" + result);

for (NodeCharacter n = result; n != null; n = n.next) {

System.out.print(" " + n.value);

}

System.out.println();

}

}

. java怎么创建链表

java中创建链表的例子：

package zx;

class Link{

private Node root;

class Node{

private String name;

private Node Next;

public Node(String name){

this.name = name;

}

public String getName(){

return this.name;

}

public void addNode(Node newNode){

if(this.Next==null){

this.Next = newNode;

}else{

this.Next.addNode(newNode);

}

}

public void printNode(){

System.out.print(this.name + "--");

if(this.Next!=null){

this.Next.printNode();

}

}

};

public void add(String name){

Node newNode = new Node(name);

if(this.root==null){

this.root = newNode;

}else{

this.root.addNode(newNode);

}

}

public void print(){

if(this.root!=null){

this.root.printNode();

}

}

};

public class LinkDemo {

/**

* @param args

*/

public static void main(String[] args) {

// TODO Auto-generated method stub

Link link = new Link();

link.add("根节点");

link.add("第一节点");

link.add("第二节点");

link.add("第三节点");

link.add("第四节点");

link.print();

System.out.println("null");

}

}

关于java链表案例和java中链表的实现的介绍到此就结束了，不知道你从中找到你需要的信息了吗 ？如果你还想了解更多这方面的信息，记得收藏关注本站。