Java数据结构——线性单链表的实现
一、描述
线性表的链式存储结构的特点：用一组任意的存储单元存储线性表的数据元素（这组存储单元可以是连续的，也可以是不连续的）。因此它没有顺序存储结构所具有的弱点（顺序存储结构插入数据或删除数据都要移动大量的数据），但同时也失去了顺序表可随机存取的优点。
单链表的组成为：数据信息和指向下一个节点的指针。
二、源码
2.1 节点信息Node.java
package com.yds.list;
public class Node<T> {
protected Node next;
protected T data;
public Node(T data){
this.data = data;
}
}
上述T为泛型
2.2 单链表的基本操作LinkList.java
package com.yds.list;
public class LinkList<T> {
public Node head;
private int position;
private int size = 0;
public LinkList(){
this.head = null;
}
/**
* 删除头结点并返回该节点
* @return
*/
public Node deleteHeadNode(){
Node tempNode = head;
head = head.next;
size--;
return tempNode;
}
/**
* 根据下标删除指定节点
* @param index
*/
public void delete(int index){
Node preNode = head;
Node tempNode = head;
if(index<0||index>size-1){
System.out.println("数组下标越界,删除失败");
return;
}else{
while(position!=index){
preNode = tempNode;
tempNode = tempNode.next;
position++;
}
preNode.next = tempNode.next;
}
position=0;
size--;
}
public int length(){
return size;
}
/**
* 通过位置来查找节点信息
* @param index
* @return
*/
public T findByPositon(int index){
T data;
Node current = head;
if(index>=0&&index<size){
while(position!=index){
current = current.next;
position++;
}
data = (T) current.data;
}else{
throw new IndexOutOfBoundsException("超出链表长度");
}
position = 0;
return data;
}
/**
* 根据数据查询该数据在链表里的位置
* @param data 需查找的数据
* @return -1到size-1;-1表示未找到，0到size-1为数据在链表里的位置
*/
public int findByData(T data){
int temp = position;
Node tempNode = head;
while(data!=tempNode.data&&position<size-1){
tempNode = tempNode.next;
position++;
}
if(data==tempNode.data)
temp = position;
else{
System.out.println("未找到");
temp = -1;
}
position = 0;
return temp;
}
/**
* 在index之前插入节点
* @param index 插入的位置
* @param data 待插入的数据
*/
public void insert(int index,T data){
Node node = new Node(data);
Node current = head;
Node preNode = head;
if(index<0&&index>size){
throw new IndexOutOfBoundsException("index 位置不合法");
}else{
while(position!=index){
preNode = current;
current = current.next;
position++;
}
preNode.next = node;
node.next = current;
size++;
position=0;
}
}
/**
* 从尾部插入数据
* @param data
*/
public void addFromTail(T data){
Node<T> node = new Node<T>(data);
Node tempNode = head;
if(head!=null){
while(position!=size-1){
tempNode = tempNode.next;
position++;
}
node.next = tempNode.next;
tempNode.next = node;
}else{
node.next = head;
head = node;
}
size++;
position = 0;
}
/**
* 头插法
* @param data
*/
public void addFromHead(T data){
Node node = new Node(data);
node.next = head;
head = node;
size++;
}
}
2.3 Main函数展示JavaMain.java
package com.yds.list;
public class JavaMain {
public static void main(String[] args) {
// TODO Auto-generated method stub
LinkList<Integer>listB = new LinkList<Integer>();
LinkList listA = new LinkList();
int[] la = {3,5,8,11};
int[] lb = {2,6,8,9,11,15,20};
System.out.println("-------尾插法---------");
for (int i = 0; i < la.length; i++) {
listA.addFromTail(la[i]);
}
for (int i = 0; i < listA.length(); i++) {
System.out.println(listA.findByPositon(i));
}
System.out.println("---------头插法----------");
for (int i = 0; i < lb.length; i++) {
listB.addFromHead(lb[i]);
}
for (int i = 0; i < listB.length(); i++) {
System.out.println(listB.findByPositon(i));
}
System.out.println("-------------------");
System.out.println("根据数据查找位置:"+listB.findByData(2));
System.out.println("根据位置查找数据:"+listB.findByPositon(listB.findByData(2)));
System.out.println("获取链表listB的长度："+listB.length());
//因为listA的数据类型为泛型（T），所以可以插入任意类型的数据，而listB只能插入整型（integer）
listA.insert(2, "ye");
System.out.println("插入数据："+listA.findByPositon(2));
System.out.println("-------------------");
listB.delete(6);
for (int i = 0; i < listB.length(); i++) {
System.out.println(listB.findByPositon(i));
}
}
}
三、结果截图 