什么是链表？
?链表 [Linked List]：链表是由一组独立的内存结构（节点）而链表是可以连续也可以不连续，按特定的顺序链接在一起的抽象数据类型。（类似数组结构）
数组和链表的区别和优缺点：
数组是一种连续存储线性结构，元素类型相同，大小相等
数组的优点：存取速度快
数组的缺点：必须先求得数组的长度时间复杂度是O(N)插入删除元素慢，限制空间需要大块连续的内存块，插入删除元素的效率很低
链表是离散存储线性结构：
彼此通过引用（指针）相连，每个节点只有一个前驱节点，每个节点只有一 个后续节点，首节点没有前驱节点，尾节点没有后续节点
链表的优点： 空间没有限制 插入删除元素很快
链表的缺点： 存取速度相对较慢
?创建链表代码如下
public class TestDemo {
static class ListNode{
public int val;//数值域
public ListNode next;//节点域
public ListNode(int val) {
this.val = val;
}
}
public ListNode head;
public void createList(){
ListNode listNode1=new ListNode(11);
ListNode listNode2=new ListNode(22);
ListNode listNode3=new ListNode(33);
ListNode listNode4=new ListNode(44);
ListNode listNode5=new ListNode(55);
ListNode listNode6=new ListNode(66);
listNode1.next=listNode2;
listNode2.next=listNode3;
listNode3.next=listNode4;
listNode4.next=listNode5;
listNode5.next=listNode6;
this.head=listNode1;
}
}?下面是实现各种模拟源码操作的方法
public boolean contains(int key){
ListNode tmp=this.head;
int sz=0;
while (tmp!=null)
{
if(tmp.val==key)
{
System.out.print("找到了在"+sz+"下标返回值为");
System.out.println("true");
return true;
}
sz++;
tmp=tmp.next;
}
System.out.print("找不到这个值返回值为");
System.out.println("false");
return false;
}//查找链表中是否包含key
public void addFirst(int data){
ListNode First=new ListNode(data);
First.next = head;
this.head = First;
}//头插法
public void addLast(int data){
ListNode Last=new ListNode(data);
if (this.head==null){
this.head=Last;
}
ListNode tmp=this.head;
while (tmp.next!=null){
tmp=tmp.next;
}
tmp.next=Last;
}//尾插法
public void addIndex(int index,int data)throws MySingleListIndexOutOfException{
ListNode Index=new ListNode(data);
checkIndexAdd(index);
if (index<=size()) {
if (index == 0 || this.head == null) {
addFirst(data);
}
else if (index == size()) {
addLast(data);
} else {
ListNode tmp = this.head;
while (index - 1 > 0) {
tmp = tmp.next;
index--;
}
Index.next = tmp.next;
tmp.next = Index;
}
}
}//指定位置添加
public void checkIndexAdd(int index){
if (index<0||index>size()){
throw new MySingleListIndexOutOfException("index坐标位置不合法");
}
}//检查坐标合法性
public void checkKey(int key){
throw new MySigleistKeyOutOfException("key值不合法");
}//检查值合法性
public void display(){
ListNode tmp=this.head;
while (tmp!=null){
System.out.print(tmp.val+" ");
tmp=tmp.next;
}
System.out.println();
}//打印单链表
public int size(){
int sz=0;
ListNode tmp=this.head;
while (tmp!=null){
sz++;
tmp=tmp.next;
}
// System.out.println(sz);
return sz;
}//获取链表长度
public void remove(int key)throws MySigleistKeyOutOfException{
ListNode tmp=this.head;
ListNode tmp1=this.head.next;
int cont=0;
if (this.head.val==key){
this.head=head.next;
cont++;
}
while (tmp!=null&&tmp1!=null)
{
if(tmp1.val==key)
{
cont++;
tmp.next=tmp1.next;
break;
}
tmp=tmp.next;
tmp1=tmp1.next;
}
if (cont==0){
checkKey(key);
}
}//删除key位置的第一个值
public void removeAll(int key){
ListNode tmp=this.head;
ListNode tmp1=this.head.next;
int cont=0;
while (tmp!=null)
{
if(tmp.val==key)
{
cont++;
tmp1.next=tmp.next;
tmp=tmp.next;
}else{
tmp1=tmp;
tmp=tmp.next;
}
}
if (this.head.val==key){
this.head=head.next;
cont++;
}
if (cont==0){
checkKey(key);
}
}//删除所有key位置的值
public void clear(){
head.next=null;
head=null;
}//清空单链表
检查坐标合法性异常?
package learn;
public class MySingleListIndexOutOfException extends RuntimeException{
public MySingleListIndexOutOfException() {
}
public MySingleListIndexOutOfException(String message) {
super(message);
}
}检查值是否合法异常?
package learn;
public class MySigleistKeyOutOfException extends RuntimeException{
public MySigleistKeyOutOfException() {
}
public MySigleistKeyOutOfException(String message) {
super(message);
}
}主函数
public class Test {
public static void main(String[] args) {
TestDemo mySingleList=new TestDemo();
mySingleList.createList();
mySingleList.display();
System.out.println("==================================");
}?部分测试
?
?
