Java---链表

目录

1.单链表

1.1单链表类

1.2 测试类

2.顺序链表

2.1顺序链表类

2.2Main函数测试类

3.循环链表

3.1单链表与循环链表的区别

3.2循环链表类

3.3测试代码:


1.单链表

1.1单链表类

package linklist;public class LinkList {class Element{public Object value=null;private Element next=null;}private Element header = null;//头结点/*** 初始化链表* */void initList(){header = new Element();header.value=null;header.next=null;}/*** 插入链表* */void insertList(Object o){Element e=new Element();e.value=o;if(header.next==null)//第一次插入元素{header.next=e;}else//不是第一次插入元素{//temp引用在栈中,temp和header引用都指向堆中的initList()中new的Element对象Element temp = header;while(temp.next!=null)//寻找最后一个元素{temp=temp.next;}temp.next=e;}}/*** 删除链表中第i个元素* */void deletelist(Object o){Element temp =header;while(temp.next!=null){//判断temp当前指向的结点的下一个结点是否是要删除的结点if(temp.next.value.equals(o)){temp.next=temp.next.next;//删除结点}else{temp=temp.next;//temp“指针”后移}}}/*** 获取链表的第i个位置的元素* */Element getElement(int i){if(i<=0 || i>size()){System.out.println("获取链表的位置有误!返回null");return null;}else{int count =0;Element element = new Element();Element temp = header;while(temp.next!=null){count++;if(count==i){element.value=temp.next.value;}temp=temp.next;}return element;}}/*** 链表长度* */int size(){Element temp = header;int size=0;while(temp.next!=null){size++;temp=temp.next;}return size;}/*** 判断链表中是否存在某元素* */Boolean isContain(Object o){Element temp =header;while(temp.next!=null){if(temp.next.value.equals(o)){return true;}temp=temp.next;}return false;}/*** 打印链表* */void print(){System.out.print("打印链表:");Element temp =header;while(temp.next!=null){temp=temp.next;System.out.print(temp.value+"\t");}System.out.println();}
}

1.2 测试类

package linklist;public class LinkListMain {public static void main(String[] args) {LinkList lList = new LinkList();lList.initList();lList.insertList(1);lList.insertList(2);lList.insertList(3);lList.insertList(4);lList.insertList(5);lList.print();lList.deletelist(2);lList.print();System.out.println("链表长度:"+lList.size());System.out.println("第1个元素值为:"+lList.getElement(1).value);System.out.println("第2个元素值为:"+lList.getElement(2).value);System.out.println("第3个元素值为:"+lList.getElement(3).value);System.out.println("第4个元素值为:"+lList.getElement(4).value);System.out.println(lList.isContain(2));System.out.println(lList.isContain(6));System.out.println(lList.isContain(5));}}

2.顺序链表

2.1顺序链表类

package list;public class SequenceList {private int LIST_INIT_SIZE = 5;//链表的原始大小private int INCREMENT =1;//链表的增量大小private Object []SqList = null;//链表private int curIndex=0;//当前位置/*** 初始化链表* */public void initList(){SqList = new Object[LIST_INIT_SIZE];}/*** 向链表中插入元素* */public void insertList(Object o){if(curIndex>LIST_INIT_SIZE-1)//判断当前链表是否已经满{//从新为链表分配空间System.out.println("从新分配空间");LIST_INIT_SIZE+=INCREMENT;Object []temp = new Object[LIST_INIT_SIZE];for(int i=0;i<curIndex;i++){temp[i]=SqList[i];}SqList=null;SqList=temp;}//链表中如果不让其包含重复元素,则加入这段代码/*if(isContain(o)){System.out.println("链表中已包含此元素"+o);}else{}*/SqList[curIndex++]= o;}/*** 判断链表中是否包含某元素* */Boolean isContain(Object o){for(int i=0;i<curIndex;i++){if(SqList[i].equals(o)){return true;}}return false;}/*** 删除链表中的某元素** 如果包含重复元素都删除* */public void delete(Object o){for(int i=0;i<curIndex;i++){if(SqList[i].equals(o)){for(int j=i;j<curIndex-1;j++){SqList[j]=SqList[j+1];}curIndex--;continue;}if(i==curIndex-1){System.out.println("不存在此元素"+o);}}}/*** 获取链表中的某个元素* */public Object getElement(int i){if (i <= 0 || i > curIndex){System.out.println("获取位置超出了链表中元素个数"+curIndex);}return SqList[i-1];}/*** 打印链表* */public void print(){for(int i=0;i<curIndex;i++){System.out.print(SqList[i]+"\t");}System.out.println();}}

2.2Main函数测试类

package list;public class SequenceListMain {public static void main(String[] args) {SequenceList sqList = new SequenceList();sqList.initList();sqList.insertList(1);sqList.insertList(2);sqList.insertList(3);sqList.insertList(4);sqList.insertList(5);sqList.insertList(6);sqList.delete(5);sqList.delete(9);sqList.insertList(1);sqList.print();sqList.delete(1);sqList.print();System.out.println("第2个元素是:"+sqList.getElement(1));System.out.println("第4个元素是:"+sqList.getElement(4));}}

3.循环链表

3.1单链表与循环链表的区别

在单链表中

 在循环链表中

 其实两者的主要差别就在于如何判断是否到了链表的结尾

3.2循环链表类

package circularlinkedlist;public class CircularLinkedList {class Element{public Object value=null;private Element next=null;}private Element header = null;//头结点/*** 初始化链表* */void initList(){header = new Element();header.value=null;header.next=header;}/*** 插入链表* */void insertList(Object o){Element e=new Element();e.value=o;if(header.next==header)//第一次插入元素{header.next=e;e.next=header;}else//不是第一次插入元素{//temp引用在栈中,temp和header引用都指向堆中的initList()中new的Element对象Element temp = header;while(temp.next!=header)//寻找最后一个元素{temp=temp.next;}temp.next=e;e.next=header;//新插入的最后一个节点指向头结点}}/*** 删除链表中第i个元素* */void deletelist(Object o){Element temp =header;while(temp.next!=header){//判断temp当前指向的结点的下一个结点是否是要删除的结点if(temp.next.value.equals(o)){temp.next=temp.next.next;//删除结点}else{temp=temp.next;//temp“指针”后移}}}/*** 获取链表的第i个位置的元素* */Element getElement(int i){if(i<=0 || i>size()){System.out.println("获取链表的位置有误!返回null");return null;}else{int count =0;Element element = new Element();Element temp = header;while(temp.next!=header){count++;if(count==i){element.value=temp.next.value;}temp=temp.next;}return element;}}/*** 链表长度* */int size(){Element temp = header;int size=0;while(temp.next!=header){size++;temp=temp.next;}return size;}/*** 判断链表中是否存在某元素* */Boolean isContain(Object o){Element temp =header;while(temp.next!=header){if(temp.next.value.equals(o)){return true;}temp=temp.next;}return false;}/*** 打印链表* */void print(){System.out.print("打印链表:");Element temp =header;while(temp.next!=header){temp=temp.next;System.out.print(temp.value+"\t");}System.out.println();}
}

3.3测试代码:

package circularlinkedlist;public class CircularLinkedListMain {public static void main(String[] args) {CircularLinkedList clList = new CircularLinkedList();clList.initList();clList.insertList(1);clList.insertList(2);clList.insertList(3);clList.insertList(4);clList.insertList(5);clList.print();System.out.println("链表长度:"+clList.size());clList.deletelist(1);clList.deletelist(5);clList.print();System.out.println("第1个元素值为:"+clList.getElement(1).value);System.out.println("第2个元素值为:"+clList.getElement(2).value);System.out.println("第3个元素值为:"+clList.getElement(3).value);System.out.println(clList.isContain(2));System.out.println(clList.isContain(6));
//      System.out.println(clList.isContain(5));}}

本文链接:https://my.lmcjl.com/post/4656.html

展开阅读全文

4 评论

留下您的评论.