数据结构——链表
数据结构——链表
本次练习主要实现数据结构链表的功能，链表主要分为单向链表和双向链表，本次练习将分别写两个类来实现这两种链表。
1.链表
链表是数据结构中的一种。数组是在内存中是一个连续的存储空间。链表是在内存中随机存储的，不需要一段连续存储空间。使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。
2.链表的组成
链表是由节点组成，其中每个节点存两种数据，分别是：数据域、引用域。链表分为：单向链表、双向链表、循环链表。本次练习主要实现单向链表、双向链表这两种链表的的功能。实现这两种链表需要头节点、尾节点这两个节点作为开始和结尾。
3.链表的实现
双向链表：尾节点和头节点作为空节点，并且分别位于链表的最开始和最末尾，头结点的top和尾节点的next都指向Null并且不参与整个链表的结点计数，函数说明：
public void add(E e)：添加值为e的结点，默认添加到链表最末尾；
public void add(E e,int loca)：添加值为e的结点，添加到下标为loca的链表位置；
public void remove(int loca) ：移除下标为loca的结点；
public void remove(E e)：移除值为e的结点；
public E get(int loca)：得到下标为loca的结点的值；
public int getSize()：得到结点个数
单向链表：和双向链表类似，只不过单向链表没有top指针，只有一个next指向下一个元素，函数说明如下：
public void add(E e)：添加值为e的结点，默认添加到链表最末尾；
public void add(E e,int loca)：添加值为e的结点，添加到下标为loca的链表位置；
public void remove(int loca) ：移除下标为loca的结点；
public void remove(E e)：移除值为e的结点；
public E get(int loca)：得到下标为loca的结点的值；
public int getSize()：得到结点个数
Doublelist.java双向链表代码如下：
package com.lxr.lianbiao0127;
import java.awt.HeadlessException;
public class Doublelist <E>{
public Node head=new Node();
public Node end=new Node();
private int size;
public Doublelist() {
head.next=end;
head.top=null;
end.next=null;
end.top=head;
size=0;
}
/**
* 添加值
* （在指定位置添加值）
* @param e
*/
public void add(E e) {
Node<E> newNode=new Node<E>();
newNode.e=e;
newNode.next=end;
if(size==0) {
head.next=newNode;
end.top=newNode;
newNode.top=head;
size++;
}
if(size>0) {
Node<E> fnode=new Node<E>();
fnode=end.top;
fnode.next=newNode;
end.top=newNode;
newNode.top=fnode;
size++;
}
}
public void add(E e,int loca) {
if(loca>=size||loca<0) {
System.out.println("位置越界");
return;
}
Node<E> newNode=new Node<E>();
newNode.e=e;
newNode.next=end;
if(size==0&&loca==0) {
head.next=newNode;
end.top=newNode;
newNode.top=head;
size++;
}
if(size>0) {
if(loca!=0) {
Node<E> node=getNode(loca);
Node<E> fnode=node.top;
fnode.next=newNode;
newNode.top=fnode;
node.top=newNode;
newNode.next=node;
size++;
}
if(loca==0) {
Node<E> node=getNode(0);
head.next=newNode;
newNode.top=head;
node.top=newNode;
newNode.next=node;
size++;
}
}
}
/**
* 移除loca位置的节点
* （参数为值）
* @param loca 删除节点的下标位置
*/
public void remove(int loca) {
if(loca>=size-1)
return;
Node<E> node=getNode(loca);
if(loca==0) {
System.out.println("移除结点的值为："+node.e);
Node<E> Nnode=node.next;
head.next=node.next;
Nnode.top=head;
}else {
System.out.println("移除结点的值为："+node.e);
Node<E> Fnode=node.top;
Node<E> Nnode=node.next;
Fnode.next=Nnode;
Nnode.top=Fnode;
}
size--;
}
public void remove(E e) {
int i;
for(i=0;i<size;i++) {
E e2=getNode(i).e;
if(e2==e)
break;
if(i==size-1) {
System.out.println("链表中没有找到此值");
return;
}
}
Node<E> node=getNode(i);
if(i==0) {
System.out.println("移除结点的值为："+node.e);
Node<E> Nnode=node.next;
head.next=node.next;
Nnode.top=head;
}else {
System.out.println("移除结点的值为："+node.e);
Node<E> Fnode=node.top;
Node<E> Nnode=node.next;
Fnode.next=Nnode;
Nnode.top=Fnode;
}
size--;
}
/**
* 得到loca位置的节点
* @param loca 节点的下标位置
* @return
*/
public E get(int loca) {
return getNode(loca).e;
}
public Node<E> getNode(int loca) {
if(loca>=size)
return null;
Node<E> node=new Node<E>();
node=head.next;
for(int i=0;i<loca;i++) {
node=node.next;
}
return node;
}
/**
* 得到结点个数
* @return
*/
public int getSize() {
return size;
}
}
singlelist.java单向链表代码如下：
package com.lxr.lianbiao0127;
import java.io.ObjectInputStream.GetField;
public class singlelist<E> {
private int size;
Node head=new Node<>();
Node end=new Node<>();
public singlelist() {
head.next=end;
end.next=null;
size=0;
}
/**
* 添加值
* （在指定位置添加值）
* @param e
*/
public void add(E e) {
Node<E> newNode=new Node<>();
newNode.e=e;
newNode.next=end;
if(size==0) {
head.next=newNode;
size++;
return;
}
if(size>0) {
//找到最后一个结点的位置
Node<E> fNode=getNode(size-1);
fNode.next=newNode;
size++;
}
}
public void add(E e,int loca) {
Node<E> newNode=new Node<>();
newNode.e=e;
if(size==0&&loca==0) {
head.next=newNode;
newNode.next=end;
size++;
return;
}
if(size>0) {
//找到位置为loca-1的结点的位置
Node<E> fNode=getNode(loca-1);
Node<E> nNode=fNode.next;
fNode.next=newNode;
newNode.next=nNode;
size++;
}
}
/**
* 移除loca位置的节点
* （参数为值）
* @param loca 删除节点的下标位置
*/
public void remove(int loca) {
System.out.println("移除结点的值为："+getNode(loca).e);
if(loca!=0) {
//找到移除结点前一个结点的位置
Node<E> fNode=getNode(loca-1);
//找到移除结点后一个结点的位置
Node<E> nNode=getNode(loca+1);
fNode.next=nNode;
size--;
}
if(loca==0) {
//找到移除结点后一个结点的位置
Node<E> nNode=getNode(loca+1);
head.next=nNode;
size--;
}
}
public void remove(E e) {
int i;
for(i=0;i<size;i++) {
Node<E> Node=getNode(i);
if(Node.e==e)
break;
if(i==size-1) {
System.out.println("链表中没有找到此值");
return;
}
}
System.out.println("移除结点的值为："+getNode(i).e+"i="+i);
if(i>0) {
//找到移除结点前一个结点的位置
Node<E> fNode=getNode(i-1);
//找到移除结点后一个结点的位置
Node<E> nNode=getNode(i+1);
fNode.next=nNode;
size--;
}
if(i==0) {
//找到移除结点后一个结点的位置
Node<E> nNode=getNode(i+1);
head.next=nNode;
size--;
}
}
/**
* 得到loca位置的节点
* @param loca 节点的下标位置
* @return
*/
public E get(int loca) {
return (E) getNode(loca).e;
}
public Node getNode(int loca) {
if(loca<0)
return null;
Node<E> Node=head;
for(int i=0;i<=loca;i++) {
Node=Node.next;
}
return Node;
}
/**
* 得到结点个数
* @return
*/
public int getSize() {
return size;
}
}
Node.java文件是结点类，代码如下：
package com.lxr.lianbiao0127;
public class Node <E>{
public E e;
public Node next;
public Node top;
}
在主main（）函数中主要测试两种链表的插入，删除，获得结点的功能是否可以实现，Manage.java代码如下：
package com.lxr.lianbiao0127;
public class Manage {
public static void main(String[] args) {
// TODO Auto-generated method stub
Doublelist<Object> doublelist=new Doublelist<>();
doublelist.add("000");
doublelist.add("111");
doublelist.add(222);
doublelist.add(333);
doublelist.add(444);
doublelist.add(555);
doublelist.add(666);
// doublelist.remove(0);
// doublelist.add("我是一个插入结点，插到i=3的位置", 3);
// doublelist.remove("000");
// doublelist.remove("0001");
// for(int i=0;i<doublelist.getSize()-1;i++) {
// System.out.println(doublelist.get(i)+"i="+i);
//
// }
singlelist<Object> singlelist=new singlelist<>();
singlelist.add("000");
singlelist.add("111");
singlelist.add(222);
singlelist.add(333);
singlelist.add(444);
singlelist.add(555);
singlelist.add(666);
// singlelist.remove(0);
singlelist.add("我是一个插入结点，插到i=3的位置", 3);
// singlelist.remove("000");
// singlelist.remove("0001");
// for(int i=0;i<singlelist.getSize();i++) {
// System.out.println(singlelist.get(i)+"i="+i);
// }
//
}
}
4.运行结果
双向链表运行结果：
单向链表运行结果相同。