数据结构之链表-单链表(1)

现在的位置: 首页 > 综合 > 正文

RSS

数据结构之链表-单链表(1)

2019年04月10日 ⁄ 综合 ⁄ 共 2177字 ⁄ 字号小中大 ⁄ 评论关闭

一、常用的4类基本结构

二、单向链表（SimpleLinked List）

1、定义Definition

2、实现Implement with Java language

3、效率Efficiency

一、常用的4类基本结构

数据结构（Data Structure）是指相互之间存在一种或多种特定关系的数据元素的集合，这种数据元素（data element）相互之间的关系称为结构（structure）。根据数据元素之间关系的不同，通常有下列4类数据结构：

（1）集合：结构中的数据元素之间除了“同属于一个集合”的关系外，别无其他关系。

（2）线性结构：结构中的数据元素之间存在一个对一个的关系。

（3）树形结构：结构中的数据元素之间存在一个对多个的关系。

（4）图状结构：结构中的数据元素之间存在一个对多个的关系。

二、单向链表（SimpleLinked List）

1、定义Definition

链表（Linked list）是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer)。单向链表的每个节点只有一个指向下一个节点地址的指针。

2、实现

（1）定义链表节点类

public class Link 
{
    public int iData;
    public Link next;
    
    public Link(int iData)
    {
    	this.iData=iData;
    }
    
    public void dispaly()
    {
    	System.out.println(iData+",");
    }
	
}

节点Link包含数据项iData和一个指向下一个节点的引用（地址）next.
(2)操作

上图中first节点不存放数据，只是作为指向第一个节点地址，表示链表的开始端。

public class SimpleLinkList 
{
	//指向第一节点ref to first link on list
	private Link first;
	
	public void SimpleLinkList()
	{
		first=null;
	}
	
	//true if link is empty
	public boolean isEmpty()
	{
		return (first==null);
	}
	
	//insert at start of list
	public void insertFirst(int iData)
	{		
		Link newLink=new Link(iData);
		newLink.next=first;
		first=newLink;		
	}

	
	//delete first item
	public Link deleteFirst()
	{
		Link tempLink=first;
		first=first.next;
		
		return tempLink;
	}
		
	public void dispalyList()
	{
		//start at begging of first
		Link current=first;
		while(current!=null)
		{
			//print data
			current.dispaly();
			//move to next link
			current=current.next;
		}
	}
	
	//find link with given key
	public Link find(int key)
	{
		Link current=first;
		
		while(current.iData !=key)
		{
			//if end of list, didn't find it
			if(current.next==null)
			{
				return null;
			}
			else
			{
				current=current.next;
			}			
		}
		
		return current;
	}
	
	public Link delete(int key)
	{
		Link current=first;
		Link previous=first;
		while(current.iData !=key)
		{
			if(current.next==null)
			{
				return null;
			}
			else
			{
				previous=current;
				current=current.next;
			}	
		}
		
		//if current refer to first, then first refer to next, because there is no previous at this situation
		if(current==first)
			first=first.next;
		else
			previous.next=current.next;
		
		return current;
	}

insertFirst方法是将节点插入链表开始端，可用下图表示该该过程