1. java链表添加数据
链表的一些方法使用和迭代器的使用（把链表内的元素迭代出），你可以看下~ import java.util.*;public class test11 {
static LinkedList list = new LinkedList();
String[] arrays = {"1","2","3","4","5"};
static Iterator it ;
public static void main(String[] args) {
test11 t = new test11();
t.useLinkedList(list);
t.useIterator(list,it);
}//链表的使用
public void useLinkedList(LinkedList list)
{
for(int i = 0;i < 5;i++)
list.add(arrays[i]);//把数组的元素都添加到链表
System.out.println("操作前的长度:"+list.size());//打印出链表的长度
System.out.println("此列表的头（第一个元素）为:"+list.peek());/*peek() 找到但不移除此列表的头（第一个元素）。*/
System.out.println("查找后的长度:"+list.size());
System.out.println("移除的元素为:"+list.poll()); /*poll() 找到并移除此列表的头（第一个元素）。*/
System.out.println("移除后的长度:"+list.size());
System.out.println("返回第一个元素:"+list.getFirst());//getFirst() 返回此列表的第一个元素。
System.out.println("返回最后一个元素:"+list.getLast());//getLast() 返回此列表的最后一个元素。
if(list.contains("4"))//boolean contains(Object o) 如果此列表包含指定元素，则返回 true。
System.out.println("存在此元素");
else
System.out.println("不存在此元素");
}//迭代器
2. 用java实现链表
单链表结构：
Java中单链表采用Node实体类类标识，其中data为存储的数据，next为下一个节点的指针：
package com.algorithm.link;
/**
* 链表结点的实体类
*
*/
public class Node {
Node next = null;//下一个结点
int data;//结点数据
public Node(int data){
this.data = data;
}
}
链表常见操作：
package com.algorithm.link;
import java.util.Hashtable;
/**
* 单链表常见算法
*
*/
public class MyLinkedList {
/**链表的头结点*/
Node head = null;
/**
* 链表添加结点:
* 找到链表的末尾结点，把新添加的数据作为末尾结点的后续结点
* @param data
*/
public void addNode(int data){
Node newNode = new Node(data);
if(head == null){
head = newNode;
return;
}
Node temp = head;
while(temp.next != null){
temp = temp.next;
}
temp.next = newNode;
}
/**
* 链表删除结点:
* 把要删除结点的前结点指向要删除结点的后结点，即直接跳过待删除结点
* @param index
* @return
*/
public boolean deleteNode(int index){
if(index<1 || index>length()){//待删除结点不存在
return false;
}
if(index == 1){//删除头结点
head = head.next;
return true;
}
Node preNode = head;
Node curNode = preNode.next;
int i = 1;
while(curNode != null){
if(i==index){//寻找到待删除结点
preNode.next = curNode.next;//待删除结点的前结点指向待删除结点的后结点
return true;
}
//当先结点和前结点同时向后移
preNode = preNode.next;
curNode = curNode.next;
i++;
}
return true;
}
/**
* 求链表的长度
* @return
*/
public int length(){
int length = 0;
Node curNode = head;
while(curNode != null){
length++;
curNode = curNode.next;
}
return length;
}
/**
* 链表结点排序,并返回排序后的头结点:
* 选择排序算法,即每次都选出未排序结点中最小的结点，与第一个未排序结点交换
* @return
*/
public Node linkSort(){
Node curNode = head;
while(curNode != null){
Node nextNode = curNode.next;
while(nextNode != null){
if(curNode.data > nextNode.data){
int temp = curNode.data;
curNode.data = nextNode.data;
nextNode.data = temp;
}
nextNode = nextNode.next;
}
curNode = curNode.next;
}
return head;
}
/**
* 打印结点
*/
public void printLink(){
Node curNode = head;
while(curNode !=null){
System.out.print(curNode.data+" ");
curNode = curNode.next;
}
System.out.println();
}
/**
* 去掉重复元素:
* 需要额外的存储空间hashtable，调用hashtable.containsKey()来判断重复结点
*/
public void distinctLink(){
Node temp = head;
Node pre = null;
Hashtable<Integer, Integer> hb = new Hashtable<Integer, Integer>();
while(temp != null){
if(hb.containsKey(temp.data)){//如果hashtable中已存在该结点，则跳过该结点
pre.next = temp.next;
}else{//如果hashtable中不存在该结点，将结点存到hashtable中
hb.put(temp.data, 1);
pre=temp;
}
temp = temp.next;
}
}
/**
* 返回倒数第k个结点,
* 两个指针，第一个指针向前移动k-1次，之后两个指针共同前进，
* 当前面的指针到达末尾时，后面的指针所在的位置就是倒数第k个位置
* @param k
* @return
*/
public Node findReverNode(int k){
if(k<1 || k>length()){//第k个结点不存在
return null;
}
Node first = head;
Node second = head;
for(int i=0; i<k-1; i++){//前移k-1步
first = first.next;
}
while(first.next != null){
first = first.next;
second = second.next;
}
return second;
}
/**
* 查找正数第k个元素
*/
public Node findNode(int k){
if(k<1 || k>length()){//不合法的k
return null;
}
Node temp = head;
for(int i = 0; i<k-1; i++){
temp = temp.next;
}
return temp;
}
/**
* 反转链表，在反转指针钱一定要保存下个结点的指针
*/
public void reserveLink(){
Node curNode = head;//头结点
Node preNode = null;//前一个结点
while(curNode != null){
Node nextNode = curNode.next;//保留下一个结点
curNode.next = preNode;//指针反转
preNode = curNode;//前结点后移
curNode = nextNode;//当前结点后移
}
head = preNode;
}
/**
* 反向输出链表，三种方式：
* 方法一、先反转链表，再输出链表，需要链表遍历两次
* 方法二、把链表中的数字放入栈中再输出，需要维护额外的栈空间
* 方法三、依据方法2中栈的思想，通过递归来实现，递归起始就是将先执行的数据压入栈中，再一次出栈
*/
public void reservePrt(Node node){
if(node != null){
reservePrt(node.next);
System.out.print(node.data+" ");
}
}
/**
* 寻找单链表的中间结点：
* 方法一、先求出链表的长度，再遍历1/2链表长度，寻找出链表的中间结点
* 方法二、：
* 用两个指针遍历链表，一个快指针、一个慢指针，
* 快指针每次向前移动2个结点，慢指针一次向前移动一个结点，
* 当快指针移动到链表的末尾，慢指针所在的位置即为中间结点所在的位置
*/
public Node findMiddleNode(){
Node slowPoint = head;
Node quickPoint = head;
//quickPoint.next == null是链表结点个数为奇数时，快指针已经走到最后了
//quickPoint.next.next == null是链表结点数为偶数时，快指针已经走到倒数第二个结点了
//链表结点个数为奇数时,返回的是中间结点；链表结点个数为偶数时，返回的是中间两个结点中的前一个
while(quickPoint.next != null && quickPoint.next.next != null){
slowPoint = slowPoint.next;
quickPoint = quickPoint.next.next;
}
return slowPoint;
}
/**
* 判断链表是否有环：
* 设置快指针和慢指针，慢指针每次走一步，快指针每次走两步
* 当快指针与慢指针相等时，就说明该链表有环
*/
public boolean isRinged(){
if(head == null){
return false;
}
Node slow = head;
Node fast = head;
while(fast.next != null && fast.next.next != null){
slow = slow.next;
fast = fast.next.next;
if(fast == slow){
return true;
}
}
return false;
}
/**
* 返回链表的最后一个结点
*/
public Node getLastNode(){
Node temp = head;
while(temp.next != null){
temp = temp.next;
}
return temp;
}
/**
* 在不知道头结点的情况下删除指定结点：
* 删除结点的重点在于找出其前结点，使其前结点的指针指向其后结点，即跳过待删除结点
* 1、如果待删除的结点是尾结点，由于单链表不知道其前结点，没有办法删除
* 2、如果删除的结点不是尾结点，则将其该结点的值与下一结点交换，然后该结点的指针指向下一结点的后续结点
*/
public boolean deleteSpecialNode(Node n){
if(n.next == null){
return false;
}else{
//交换结点和其后续结点中的数据
int temp = n.data;
n.data = n.next.data;
n.next.data = temp;
//删除后续结点
n.next = n.next.next;
return true;
}
}
/**
* 判断两个链表是否相交：
* 两个链表相交，则它们的尾结点一定相同，比较两个链表的尾结点是否相同即可
*/
public boolean isCross(Node head1, Node head2){
Node temp1 = head1;
Node temp2 = head2;
while(temp1.next != null){
temp1 = temp1.next;
}
while(temp2.next != null){
temp2 = temp2.next;
}
if(temp1 == temp2){
return true;
}
return false;
}
/**
* 如果链表相交，求链表相交的起始点：
* 1、首先判断链表是否相交，如果两个链表不相交，则求相交起点没有意义
* 2、求出两个链表长度之差：len=length1-length2
* 3、让较长的链表先走len步
* 4、然后两个链表同步向前移动，没移动一次就比较它们的结点是否相等，第一个相等的结点即为它们的第一个相交点
*/
public Node findFirstCrossPoint(MyLinkedList linkedList1, MyLinkedList linkedList2){
//链表不相交
if(!isCross(linkedList1.head,linkedList2.head)){
return null;
}else{
int length1 = linkedList1.length();//链表1的长度
int length2 = linkedList2.length();//链表2的长度
Node temp1 = linkedList1.head;//链表1的头结点
Node temp2 = linkedList2.head;//链表2的头结点
int len = length1 - length2;//链表1和链表2的长度差
if(len > 0){//链表1比链表2长，链表1先前移len步
for(int i=0; i<len; i++){
temp1 = temp1.next;
}
}else{//链表2比链表1长，链表2先前移len步
for(int i=0; i<len; i++){
temp2 = temp2.next;
}
}
//链表1和链表2同时前移,直到找到链表1和链表2相交的结点
while(temp1 != temp2){
temp1 = temp1.next;
temp2 = temp2.next;
}
return temp1;
}
}
}
测试类：
package com.algorithm.link;
/**
* 单链表操作测试类
* @author bjh
*
*/
public class Test {
public static void main(String[] args){
MyLinkedList myLinkedList = new MyLinkedList();
//添加链表结点
myLinkedList.addNode(9);
myLinkedList.addNode(8);
myLinkedList.addNode(6);
myLinkedList.addNode(3);
myLinkedList.addNode(5);
//打印链表
myLinkedList.printLink();
/*//测试链表结点个数
System.out.println("链表结点个数为：" + myLinkedList.length());
//链表排序
Node head = myLinkedList.linkSort();
System.out.println("排序后的头结点为：" + head.data);
myLinkedList.printLink();
//去除重复结点
myLinkedList.distinctLink();
myLinkedList.printLink();
//链表反转
myLinkedList.reserveLink();
myLinkedList.printLink();
//倒序输出/遍历链表
myLinkedList.reservePrt(myLinkedList.head);
//返回链表的中间结点
Node middleNode = myLinkedList.findMiddleNode();
System.out.println("中间结点的数值为："+middleNode.data);
//判断链表是否有环
boolean isRinged = myLinkedList.isRinged();
System.out.println("链表是否有环：" + isRinged);
//将链表的最后一个结点指向头结点，制造有环的效果
Node lastNode = myLinkedList.getLastNode();
lastNode.next = myLinkedList.head;
isRinged = myLinkedList.isRinged();
System.out.println("链表是否有环：" + isRinged);
//删除指定结点
Node nk = myLinkedList.findReverNode(3);
System.out.println(nk.data);
myLinkedList.deleteSpecialNode(nk);
myLinkedList.printLink();
//链表是否相交
//新链表
MyLinkedList myLinkedList1 = new MyLinkedList();
myLinkedList1.addNode(1);
myLinkedList1.addNode(2);
myLinkedList1.printLink();
System.out.println("链表一和链表二是否相交"+myLinkedList.isCross(myLinkedList.head, myLinkedList1.head));
//把第二个链表从第三个结点开始接在第二个链表的后面，制造相交的效果
myLinkedList1.findNode(2).next = myLinkedList.findNode(3);
myLinkedList1.printLink();
System.out.println("链表一和链表二是否相交"+myLinkedList.isCross(myLinkedList.head, myLinkedList1.head));
*/
//如果两个链表相交求链表相交的结点的值
MyLinkedList myLinkedList1 = new MyLinkedList();
myLinkedList1.addNode(1);
myLinkedList1.addNode(2);
myLinkedList1.findNode(2).next = myLinkedList.findNode(3);
myLinkedList1.printLink();
Node n = myLinkedList1.findFirstCrossPoint(myLinkedList, myLinkedList1);
if(n == null){
System.out.println("链表不相交");
}else{
System.out.println("两个链表相交，第一个交点的数值为：" + n.data);
}
}
}
3. java 创建链表
链表的由来
一、链表的由来
我们接触最多的数据存储结构应该是数组了，在实际场景中它的出现频率极高，但是它并不能适于用所有情况。这也是的链表
原因如下：
在很多编程语言中，数组的长度是固定的，所以当数组已被数据填满时，再要加入新的元素就会非常困难。
在数组中的添加和删除元素很麻烦，因为需要将数组中的其他元素向前或向后平移。
JavaScript中数组的主要问题是，它们被实现成了对象，与其他语言（比如 C++ 和 Java） 的数组相比，效率较低。
为了解决上述问题如果你发现数组在实际使用时很慢，就可以考虑使用链表来替代它。除了对数据的随机访问，链表几乎可以用在任何可以使用一维数组的情况中，如果需要频繁的删除和添加操作，就主动考虑一下链表吧～
1.1 特点
优点
链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。
增加数据和删除数据很容易。
链表中的每个元素实际上是一个单独的对象，而所有对象都通过每个元素中的引用字段链接在一起。
缺点？
访问时间是线性的(而且难以管道化)，更快的访问，如随机访问，是不可行的。与链表相比，数组具有更好的缓存位置。
失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大
链表有很多种不同的类型：单向链表，双向链表以及循环链表。链表可以在多种编程语言中实现。下面出现的代码都是用Js实现的，如果不对的地方，欢迎大佬们指正，我们共勉。
二、单链表
单链表中的每个结点不仅包含值，还包含链接到下一个结点的引用字段。通过这种方式，单链表将所有结点按顺序组织起来。、
下面是一个单链表的例子：
当你得到了head节点，就得到了整个列表。
我们创建单一节点（Node）的操作应该是这样的：
2.1 添加节点
就像给绳子打结一样，添加节点，就是在两个绳结之间，再打一个新结。
如果我们想在给定的结点 prev 之后添加新值，我们应该：
创建要插入的Node——cur
将cur节点的next链接到next节点（pre的下一个节点）
将pre的next链接到cur节点
在开头添加结点
众所周知，我们使用头结点（head）来代表整个列表。
因此，在列表开头添加新节点时更新头结点 head 至关重要。
初始化一个新结点 cur；
将新结点cur的next链接到我们的原始头结点 head.next节点
将head节点的next链接到cur即可。
在末尾添加节点
创建新节点cur
将链表的末尾节点的next链接到cur即可
2.2 删除节点
如果我们要删除指定的节点cur，该这么做：
找到cur的上一个节点prev，及其下一个节点prev.next（要删除的节点）
将prev.next链接让 `prev.next.next，即跳过删除节点。
注意：我们必须从头节点遍历至指定节点，删除节点的平均时间复杂度是O(N)
删除末尾节点
找到next节点链接为null的节点，以及它的前节点prev
prev.next 链接 null 即可
三、设计链表
以LeetCode的中的基础题为例，我们尝试用代换实现前文提过的思路。707.设计链表
题目
设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性：val 和 next。val 是当前节点的值，next 是指向下一个节点的指针/引用。如果要使用双向链表，则还需要一个属性 prev 以指示链表中的上一个节点。假设链表中的所有节点都是 0-index 的。
在链表类中实现这些功能：
get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。
示例：
Js版代码实现
为了方便操作，我们主动创建了一个节点为头节点，实际存储过程中是完全不需要的。
四、链表的基本使用场景
对线性表的长度或者规模难以估计；
频繁做插入删除操作；
构建动态性比较强的线性表
链表的基本操作
1.创建节点
2.创建链表
3.查找目标节点
4.添加操作
5.查找存储目标节点的节点
6.删除操作
7.打印操作
测试数据
4. java链表的使用
可以一重循环，获取其中一个集合的keyset，遍历keyset，取出两个value合并成你要的新集合
5. java怎么创建一个链表
链表是一种数据结构，和数组同级。比如，Java中我们使用的ArrayList，其实现原理是数组。而LinkedList的实现原理就是链表了。链表在进行循环遍历时效率不高，但是插入和删除时优势明显。
链表就是链式存储的线性表。根据指针域的不同，链表分为单向链表、双向链表、循环链表等等。
- 相关评论
- 我要评论
-
